3

設定された数の整数に対して、1 から最大までのすべての可能な一意の整数の組み合わせを出力しようとしています。したがって、3 つの整数と最大 4 の場合、次のようになります。

123 124 134 234

ネストされた for ループでこれを行っていますが、実行時にユーザーが整数の数を入力できるようにしたいと考えています。今私は持っています

if(numInts >6);
for(int x = 1; x < max; x++);
if(numInts >5);
for(int y = 1; y < max; y++);
...

これをクリーンアップする方法はありますか?ループの可能な整数をそれぞれ書き出す必要はありません。

PS: 上記のコードでは、要求された出力が出力されないことはわかっています。これはプログラミング コンテストのためのものなので、これを可能にするアイデアだけをコード ソリューションに求めているわけではありません。

4

6 に答える 6

3

一言：再帰。

于 2009-11-23T16:28:14.560 に答える
1

元の投稿に対するコメントを見ると、反復的な解決策が必要です。末尾呼び出しの最適化をサポートする言語がある場合、再帰的なソリューションは反復的なソリューションと同じくらい高速になります。ただし、Java / C＃を使用している場合も、これは利用できないため、問題を調べる別の方法があります。

組み合わせを生成しています。組み合わせは、特定の数の要素を持つサブセットにすぎません。小さめのセットを持つサブセットは、ビットマスクで表現できます。

セットが[1, 2, 3, 4]あり、サブセットを説明したい場合は[1, 3, 4]、各要素を調べて「TrueまたはFalse：この要素はサブセットに含まれていますか？」と尋ねることで説明できます。したがって、の[1, 3, 4]場合、結果は[True, False, True, True]です。32（または64）バイト未満のセットで作業している場合、これを整数としてエンコードできます：1011b =11。これはメモリ内で非常にコンパクトであり、コンピューターは非常に高速なビット演算演算子を備えている傾向があります。

では、これらの2進数に関して、組み合わせは何でしょうか。N個のメンバーを持つすべてのサブセットが必要な場合は、「Nビットが設定されたすべての数値が必要」と解釈できます。

私[1, 2, 3, 4]たちがそうであったように取ってください。3つの要素を持つすべてのサブセットが必要です。正確に3ビットが設定された4ビットの数値はいくつありますか？回答：1110b、1101b、1011b、および0111b。これらの整数をサブセットに変換すると、、、、、および[1, 2, 3]の解[1, 2, 4]が得られます。[1, 3, 4][2, 3, 4]

あなたはビットだけの観点から考え始めることができます。Nビットを設定した最小の数値から始めます。それは解決策に対応します。次に、ビットを1対1で反転し始めます。各反復が常に次に大きい数になるような体系的な方法で。

于 2009-11-23T17:12:07.153 に答える
1

再帰を使用numIntsして、コール ツリーの深さになります。

于 2009-11-23T16:28:26.790 に答える
1

ウィキペディアで組み合わせを調べてください。これらはあなたが生成しようとしているものです。

編集：最初、OPは順列を意味すると思いました。次のコードは組み合わせでは機能しませんが、機能させるために微調整したい場合に備えて、ここに残しておきます。

他の人が言ったように、これは再帰が得意とする問題です。関数を呼び出しましょうpick(num, list)。ここにいくつかの擬似コードがあります。

List pick(Int num, List list)
{
  if (num == 1) // base case
  {
    return list
  }
  else // recurring case
  {
    var results = []
    foreach (item in list)
    {
      alteredList = list.copy().remove(item)
      results.add([item] + pick(num - 1, alteredList))
    }
    return results
  }
}

上記のコードに関するいくつかのメモ。2 つのケースに注意してください。再帰は、ほとんどの場合、base-case/recurring-case 形式に従います。実際の再帰は行results.add([item] + pick(num - 1, alteredList))で発生し、重要なポイントは渡すことですnum-1。これは、 への呼び出しのたびにpick、numが到達するまでどんどん小さくなっていく1( に到達する1と完了) ことを意味します。

指定された変数alteredListは、現在のアイテムが削除されたリストの COPY として作成されます。ほとんどの言語にはremovedメソッドがありますが、元のリストを変更します (これはあなたが望むものではありません!!)。

最後に、その線引きを少し明確にしたいと思い[item] + pick(num - 1, alteredList)ます。item最初の要素がで、残りの要素が呼び出しによって返されるリストである新しいリストを作成することを意味しますpick(num - 1, alteredList)。Lisp では、リストの前に要素を追加するこの操作を a と呼びますcons。このcons操作は、再帰が頻繁に使用される関数型言語では非常に強力ですが、Java/C# などの命令型言語で表現するのは厄介です。

于 2009-11-23T16:58:13.080 に答える
0 
internal class Program {
    private static void Main(string[] args) {
        foreach (var combination in AllCombinations(new[] { 1, 2, 3 })) {
            Console.WriteLine(string.Join("", combination.Select(item => item.ToString()).ToArray()));
        }
    }

    private static IEnumerable<IEnumerable<T>> AllCombinations<T>(IEnumerable<T> elements) {
        if (elements.Count() == 1) yield return new[] { elements.First() };
        else {
            foreach (var element in elements) {
                foreach (var combination in AllCombinations(elements.Except(new[] { element }))) {
                    yield return (new[] { element }).Concat<T>(combination);
                }
            }
        }
    }
}
于 2009-11-23T16:34:47.463 に答える
0

ネストされた for ループが必要な問題は、通常、再帰を求めます。

のような木を想像してください。

<root>
    <1>
       <1>
          <1>
          <2>
          <3>
          <4>
       <2>
          <1>
          <2>
          <3>
          <4>
    ...

次に、ツリーを (再帰的に) 歩き、「有効なパス」を収集します。

于 2009-11-23T16:39:07.703 に答える