配列のパーティションの最小値の差

Question

C＃/ Javaの最小の違いに応じて配列データを分割する必要があります。

Input: { A1, A2, B3, D4, C7, B12, A12, C14, D15, C22, A23, B25, A35, A36, D37 } 

• B3、D4 = | 3 - 4の差| = 1

• A23、B25の差= | 23-25 | = 2

• D4、C7の差= | 4 - 7 | = 3

• B12、A12の差= | 12-12 | = 0

規則がある： - 4要素

違い各群について

• 、文字は各群について

• 繰り返すことができない、それは1を含んでき要素間の距離は< = 3

---

Output: { A1 },{ A2, B3, D4, C7 },{ B12, A12, C14, D15 },{ C22, A23, B25 },{ A35 },{ A36, D37 } 

Answer 1

Dyalog APLパラレルアレイ処理言語でコードするのに10分しかかかりませんでしたが、答えを書き留めるのに2時間かかりました。私はすべてのコードを提出するつもりはないので、質問の言語の制約を壊さないために、私はデータといくつかの擬似コードを使って、以下の原則を明確にしようとします。

┌──────────┬─┬─┬──┬──┬───┬───┬──┬──┬──┬──┬─────┐ 
│Partitions│6│7│8 │9 │10 │11 │12│13│14│15│Total│ 
├──────────┼─┼─┼──┼──┼───┼───┼──┼──┼──┼──┼─────┤ 
│Solutions │1│9│36│84│126│126│84│36│9 │1 │512 │ 
└──────────┴─┴─┴──┴──┴───┴───┴──┴──┴──┴──┴─────┘ 

最小のパーティションを持つ溶液（6）である：

┌──┬───────────┬───────────────┬───────────┬───┬───────┐ 
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│ 
└──┴───────────┴───────────────┴───────────┴───┴───────┘ 

引数が固定順序を有し、以下のように、512の可能な解決策があることを提供

次のパーティション（7つのパーティション）は次のとおりです。

┌──┬───────────┬───────────────┬───────────────┬───────────┬───┬───────┐ 
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23 B25 │A35  │A36│D37 │ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22 A23  │B25  │A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 C7│B12 A12 C14 D15│C22   │A23 B25 │A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 C7│B12 A12 C14 │D15   │C22 A23 B25│A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 C7│B12 A12  │C14 D15  │C22 A23 B25│A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 C7│B12   │A12 C14 D15 │C22 A23 B25│A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3 D4 │C7    │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2 B3  │D4 C7   │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│ 
├──┼───────────┼───────────────┼───────────────┼───────────┼───┼───────┤ 
│A1│A2   │B3 D4 C7  │B12 A12 C14 D15│C22 A23 B25│A35│A36 D37│ 
└──┴───────────┴───────────────┴───────────────┴───────────┴───┴───────┘ 

（15のパーティションへの）最後のものは当然です：

┌──┬──┬──┬──┬──┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ 
│A1│A2│B3│D4│C7│B12│A12│C14│D15│C22│A23│B25│A35│A36│D37│ 
└──┴──┴──┴──┴──┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘ 

これは最高の、最も安全な方法は、この問題は、ブルートフォースを使用して解決し、あらゆる可能性を歩くために。最初に、パーティションの場所を示すためにゼロと1を使用するという原則を適応させる必要があります。引き数には15の要素があるので、私たちは15の長さのバイナリーベクトルを使って作業を行います。例：

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition (1 1 0 0 1 1 0 1 0 0 0 1 1 0 0) 

は返還しなければならない：

┌─────┬─────────┬─────┬───────┐ 
│1 1 0│0 1 1 0 1│0 0 0│1 1 0 0│ 
└─────┴─────────┴─────┴───────┘ 

┌───┬─────┬───┬────┐ 
│sta│ckove│rfl│owex│ 
└───┴─────┴───┴────┘ 

あなたはまた、別の15-長ブールベクトルを分割することができます

(1 0 0 1 0 0 0 0 1 0 0 1 0 0 0) partition 'stackoverflowex' 

は/ 4のパーティションを返還しなければならない意味します

と計算することができます各パーティションにはの合計。上記のいずれかが返されます：

┌─┬─┬─┬─┐ 
│2│3│0│2│ 
└─┴─┴─┴─┘ 

をあなたの問題を解決するには、可能なすべてのパーティションベクトルを生成する必要があります。これは言ったより簡単です。

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // This would create 1 single, big partition 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 // This would create 15 small partitions 

これらはどういう意味ですか？非常に単純ですが、16384と32767の2ベース（バイナリ）表現です。16384〜32767（両端を含む）のすべての数字をループし、各数字を2進数に変換し、現在のパーティションが受け入れ可能かどうかを確認してください（=「あなたの条件を満たす、グループごとに文字を繰り返すことはできません」など）。間隔内のすべての数値を変換するとはすべての可能なパーティションをカバーします - ゼロと1の可能な組み合わせがそこにあります。計算には1秒の断片しかかかりません。

擬似：残りの部分はいくつかのテストに失敗しながら、この時点で

// The character part of the argument: 15-length vector of characters: 
Chars = "A","A","B","D","C","B","A","C","D","C","A","B","A","A","D" 

// From that, extract the locations of the unique characters: 
CharsA = 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0 // Where Chars == A 
CharsB = 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 // Where Chars == B 
CharsC = 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0 // Where Chars == C 
CharsD = 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 // Where Chars == D 

// The numeric part of the argument: 15-length vector of numbers: 
// Btw, is this about lottery... hmmm 
Nums = 1, 2, 3, 4, 7, 12, 12, 14, 15, 22, 23, 25, 35, 36, 37 

:For Number :In [all numbers between 16384 and 32767] 

    Base2 = [2-base of Number] // 2would give: 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 

    // Test 1: "For each group, it can contains 1 - 4 elements" 
     [using Base2, partition the partition vector Base2 itself; 
     bail out if any partition length exceeds 4] 

    // Test 2: "Difference between element must be <= 3" 
     [using Base2, partition Nums; 
     check differences inside each partition; 
     bail out if bigger than 3 anywhere] 

    // Test 3: "For each group, letter cannot be repeated" 
     [using Base2, partition CharsA, CharsB, CharsC, CharsD (each in turn); 
     count number of ones in each partition; 
     bail out if exceeds 1 anywhere (meaning a character occurs more than once)] 

    // If we still are here, this partition Number is ACCEPTABLE 
    [add Number to a list, or do a parallel boolean marking 1 for Number] 

:End 

、512番号のは、指定された条件を満たしました。それは純粋な偶然のことであり、それは私たちのコーダーにとって特別な数字である512であった。 結果という変数に受け入れ可能な512の数値があるとします。今度は、各Result内のパーティション数を解決することで、ソートする必要があります（=バイナリ表現の1の数）。Resultの各数値を再び基数2に変換してから、それぞれ&を数え、その合計での昇順でをソートします。最小の合計は6になり、1回だけ発生します。これはこの回答の先頭に記載されたパーティションです。

それが価値だが25126であり、そのための2塩基は

1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 

Answer 2

あなたが提供された入力は、複数のソリューションが含まれています。おそらく約15程度（A1-A2、A35-A36、D4-C7は解決策を変えるものです）。私はあなたが望んでいたそのソリューション尋ねられたときあなたは答えなかったので、私はこの1つ、この問題のための（最も簡単な）「ソリューション」を与えるコード=）

static string[][] Solve(string[] input) 
{ 
    List<string> myList = new List<string>(input); 
    List<string[]> groups = new List<string[]>(); 
    while (myList.Count > 0) 
    { 
     string currentStr = myList[0]; 
     int currentNum = int.Parse(currentStr.Substring(1)); 
     List<string> lessThan4 = new List<string>(); 
     lessThan4.Add(currentStr); 
     for (int i = 1; i < myList.Count; i++) 
     { 
      if (Math.Abs(currentNum - int.Parse(myList[i].Substring(1))) < 4) 
      { 
       // Add it to the list only if there's not the same letter in there 
       if (!lessThan4.Where(a => a.Contains(myList[i].Substring(0, 1))).Any()) 
       { 
        lessThan4.Add(myList[i]); 
       } 
      } 
     } 

     lessThan4.Sort(); 
     groups.Add(lessThan4.ToArray()); 
     myList = myList.Except(lessThan4).ToList(); 
    } 
    return groups.ToArray(); 
} 

はあなたが好きなものでそれをテストすることができますを書きました：

重要

{ A2, B3, D4 },{ C7 },{ B12, A12, C14, D15 },{ C22, A23, B25 },{ A35, D37 },{ A36 } 

：このコードはINP内部文字列と仮定されること場合

string[] input = new string[] { "A2", "B3", "D4", "C7", "B12", "A12", "C14", "D15", "C22", "A23", "B25", "A35", "A36", "D37" }; 
Solve(input); 

（解決の出力） utはユニークです。