2

脑筋急转弯：我自己提出了这个问题，但完全卡住了。

我想创建所有字符的所有可能组合，但具有所有可能的长度。假设，[az] 组合 1 个长度，然后 [az] 组合 2 个长度，依此类推，直到达到最大长度。

这可以通过迭代循环很容易地完成。

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 回答