2

頭の体操: この質問は自分で考えたのですが、完全に行き詰まってしまいました。

すべての文字の可能なすべての組み合わせを作成したいのですが、すべての可能な長さです。1 つの長さの [az] の組み合わせ、次に 2 つの長さの [az] の組み合わせというように、最大​​の長さに達するまで続けます。

これは、反復ループによって非常に簡単に実行できます。

3 長さの例:

proc triples list {
    foreach i $list {
        foreach j $list {
            foreach k $list {
                puts [list $i $j $k]
            }
        }
    }
}

ただし、より少ないループを使用して解決する必要があります (ループは動的である必要があります)。

set chars "abcdefghijklmnopqrstuvwxyz"
set chars [split $chars ""]

set complete_length [llength $chars]

set start 0
set maximum_length 15


while {1} {
    if {$start > $maximum_length} {
        break
    }
    for {set i [expr $maximum_length-$start]} {$i >= 0} {incr i -1} {
        # dump combinations
    }
    incr start
}

このチャンクでは、どのアルゴリズムまたはメソッドを適用する必要がありますか? あらゆる種類の提案/ヘルプ/コードをいただければ幸いです。

4

1 に答える 1

0

申し訳ありませんが、これは答えではありませんが、とにかく興味深い議論を期待しています:

「組み合わせ」という言葉はあまりにも一般的に使用されることが多いため、さまざまな方法で解釈できます。26 の異なる要素 (英語の文字) のソース リストがあり、そのうちの 3 つを選択して 3 つの要素の宛先リストに結合するとします。

  • ソースリストからいつでも任意の文字を選択できますか?それとも、選択すると要素が消えますか? 「ピック」(ピック中にコピーまたは移動された要素) を定義するか、ソース値のセットを定義します (各 AZ が 1 つあるのか、AZ が無限に存在するのか)。
  • 宛先リストの順序は重要ですか? は?AHMと同じ組み合わせと見なされます。HAM「結合」を定義します。
  • {2 10 10 64 100} のように、すべての要素が異なるわけではないリストがある場合、さらに多くの可能性があります。一連の値を定義します。

最初の例では、組み合わせではなく順列を出力します。それがあなたが望むものなら、最も簡単な方法は再帰的な手順です。組み合わせを生成するのはより複雑です。

編集：

Project Euler プログラム用にこの手順を書きました。すべての要素を選択しますが、n を選択するように変更することもできます。コマンドプレフィックスを引数として取るため、すべての順列を保存する必要はありません。

package require Tcl 8.5.0

proc forEachPerm {list cmdPrefix} {
  _forEachPerm {} $list $cmdPrefix
}

proc _forEachPerm {head list cmdPrefix} {
  if {![llength $list]} {
    {*}$cmdPrefix $head
  } else {
    for {set i 0} {$i < [llength $list]} {incr i} {
      _forEachPerm [concat $head [lrange $list $i $i]] [lreplace $list $i $i] $cmdPrefix
    }
  }
}

# example use:
forEachPerm {a b c} {apply {{list} {puts [join $list]}}}
于 2013-10-02T07:21:55.380 に答える