arrays - 1 ～ 10 要素の配列の 4 つの数値が与えられます。合計すると 4 つの数すべてを生成できる 3 つの数を見つけますか?

Question

4 つの乱数 (1 から 10 まで) のリストを含む配列が与えられます。生成されたリストの 3 つの数字を追加することにより、初期リストの 4 つの数字すべてを生成できるように、3 つの数字 (1 から 10 を含む) のリストを生成することになっています。

誰かこれを行うためのアルゴリズムを提供してください。

Answer 1

ソリューションには 1 ～ 10 の範囲にある 3 つの数値しか含まれていないため、ここではブルート フォースが効果的なアルゴリズムです (素朴な実装でも最大 1000 の可能性をチェックできます)。したがって、C# コードは次のようになります。

public static int[] BruteForce(int[] data) {
  HashSet<int> hs = new HashSet<int>();

  for (int x = 1; x <= 10; ++x)
    for (int y = x; y <= 10; ++y)
      for (int z = y; z <= 10; ++z) {
        hs.Clear();

        for (int i = 0; i < data.Length; ++i)
          hs.Add(data[i]);

        hs.Remove(x);
        hs.Remove(y);
        hs.Remove(z);

        hs.Remove(x + y);
        hs.Remove(x + z);
        hs.Remove(y + z);

        hs.Remove(x + y + z);

        if (hs.Count <= 0) 
          return new int[] { x, y, z }; // <- Solution
      }

  return new int[] {}; // <- No solution found
}

いくつかのテストケース:

1. BruteForce(new int[] {1, 3, 7, 8}); // <- [1, 2, 5]
2. BruteForce(new int[] {1, 3, 7, 9}); // <- [1, 2, 6]
3. BruteForce(new int[] {1, 6, 7, 9}); // <- [1, 2, 6]; 前のケースと同じ
4. BruteForce(new int[] {4, 6, 7, 9}); // <- [1, 3, 6]
5. BruteForce(new int[] {5, 6, 7, 9}); // <- [2, 3, 4]
6. BruteForce(new int[] {1, 2, 4, 8}); // <- 解決策が見つかりません

問題セット(1 ～ 10 の範囲にある 4 つのアイテムのすべての可能なリスト) でさえ、上記で実装されたブルート フォース アルゴリズムによって解決されるほど十分に小さい (10000 アイテム)。10000 から 768 の 4 項目リストだけが 3 項目リストで生成できないことは簡単にわかります。