Tcl 中的递归编程用于排列

Question

我有一个未知的模式，以及提供给我的getCombos进程的未知数据量。

我需要找到一种方法，在模式允许的情况下递归地在数据中生成尽可能多的匹配项。

例如：

# pattern  | data
# {0 1 2}    {0 {{A B C} {AA BB CC}}
              1 {{D E F} {DD EE FF}}
              2 {{G H I} {GG HH II}}
             }
# returns this list: (split out on multiple lines are for your viewing pleasure)
  { A  E  I  }
  { A  E  II }
  { A  EE I  }
  { A  EE II }
  { AA E  I  }
  { AA E  II }
  { AA EE I  }
  { AA EE II }

数据将始终是一个字典列表，其中键从 0 到 n。

模式将始终是 0 到 n 的混合（在本例中为 {0 1 2} 或 {2 0 1} 等）。

这就是我认为我无法使用简单递归的原因 - 因为我不知道模式中有多少元素，也不知道数据下每个值中有多少元素，也不知道数据中会有多少键。

我唯一知道的是，数据值元素内的元素数量与模式中的元素数量匹配（例如。 [llength {0 1 2}]是 3，[llength {A B C}]是 3），这非常重要，因为我按该顺序从$data中提取数据。

请允许我举一个反例来强调模式影响它的方式：

# pattern  | data
# {1 2 1}    {0 {{A B C} {AA BB CC}}
              1 {{D E F} {DD EE FF}}
              2 {{G H I} {GG HH II}}
             }
# returns this list: (split out on multiple lines are for your viewing pleasure)
  { D  H  F  }
  { D  H  FF }
  { D  HH F  }
  { D  HH FF }
  { DD H  F  }
  { DD H  FF }
  { DD HH F  }
  { DD HH FF }

正如你在上面的例子中看到的[dict get $data 0]从未输入过任何等式。模式的第一个索引对应于值列表中第一个分组中的第一项（A AA D DD G 和 GG），第二个与第二个（B BB E EE H 或 HH）匹配，第三个与第三个（C CC F FF I 或 II）匹配。这些索引的实际值与应使用的键匹配。

最后，我需要根据模式对适当数据进行每种组合。

相当令人困惑。这是我一直在走的路，但正如你所看到的，我远没有任何有价值的东西：

proc getCombo {pattern data} {
  set g yes
  set i 0  ;# These counters must be replaced by recursive design
  set j 0
  set k 0
  set p 0
  while {$g} {
    puts [lindex [lindex [dict get $data $i] $j] [lindex $pattern $p]]
    puts " [lindex [lindex [dict get $data $j] $k] [lindex $pattern $p]]"
    if {$k == [llength [dict get $data $i]] } {
      set k 0
      set g no
    }
    if {$j == [llength [dict get $data $i]] } {
      set j 0
      incr k
      incr p
    }
    incr j
  }
#########################
  for {set z 0} {$z < [llength [dict get $data 0]]} {incr z} {
    for {set o 0} {$o < [llength [dict get $data 1]]} {incr o} {
      for {set t 0} {$t < [llength [dict get $data 2]]} {incr t} {
        for {set p 0} {$p < [llength $pattern]} {incr p} {
        }
      }
    }
  }
########################
  #foreach pat $pattern {
    foreach key [dict keys $data] {
    }
  #}
########################
  #return $newdata
}

有人知道我能在这里做什么吗？我花了一整天的时间才想出上面的代码，我并没有感觉更接近，但我现在有一种感觉，如果我要产生我想要的东西，我的 proc 需要递归。

感谢您给我的任何建议或指导！

Answer 1

编辑

下面给出了示例中的子集。

set input {
  {1 2 1}
  {
    0 {{A B C} {AA BB CC}}
    1 {{D E F} {DD EE FF}}
    2 {{G H I} {GG HH II}}
  }
}
set pattern [lindex $input 0]
set data [lindex $input 1]
proc perm {pattern data {start 0} {result ""}} {
  set len [llength $pattern]
  set rlen [llength $result]
  if {$rlen == $len} {
    puts [join $result "t"]
    return
  }
  for {set i $start} {$i < $len} {incr i} {
    set k [lindex $pattern $i]
    foreach {subset} [dict get $data $k] {
      set temp $result
      lappend temp [lindex $subset $rlen]
      perm $pattern $data [expr {$i + 1}] $temp
    }
  }
}
perm $pattern $data

输出：

D   H   F
D   H   FF
D   HH  F
D   HH  FF
DD  H   F
DD  H   FF
DD  HH  F
DD  HH  FF

全烫发

set input {
  {1 2 1}
  {
    0 {{A B C} {AA BB CC}}
    1 {{D E F} {DD EE FF}}
    2 {{G H I} {GG HH II}}
  }
}
set pattern [lindex $input 0]
set data [lindex $input 1]
proc perm {pattern data {start 0} {result ""}} {
  set len [llength $pattern]
  if {[llength $result] == $len} {
    puts [join $result "t"]
    return
  }
  for {set i $start} {$i < $len} {incr i} {
    set k [lindex $pattern $i]
    foreach {subset} [dict get $data $k] {
      foreach {value} $subset {
        set temp $result
        lappend temp $value
        perm $pattern $data [expr {$i + 1}] $temp
      }
    }
  }
}
perm $pattern $data

输出：

D   G   D
D   G   E
D   G   F
D   G   DD
D   G   EE
D   G   FF
D   H   D
D   H   E
D   H   F
D   H   DD
D   H   EE
D   H   FF
D   I   D
D   I   E
D   I   F
D   I   DD
D   I   EE
D   I   FF
D   GG  D
D   GG  E
D   GG  F
D   GG  DD
D   GG  EE
D   GG  FF
D   HH  D
D   HH  E
D   HH  F
D   HH  DD
D   HH  EE
D   HH  FF
D   II  D
D   II  E
D   II  F
D   II  DD
D   II  EE
D   II  FF
E   G   D
E   G   E
E   G   F
E   G   DD
E   G   EE
E   G   FF
E   H   D
E   H   E
E   H   F
E   H   DD
E   H   EE
E   H   FF
E   I   D
E   I   E
E   I   F
E   I   DD
E   I   EE
E   I   FF
E   GG  D
E   GG  E
E   GG  F
E   GG  DD
E   GG  EE
E   GG  FF
E   HH  D
E   HH  E
E   HH  F
E   HH  DD
E   HH  EE
E   HH  FF
E   II  D
E   II  E
E   II  F
E   II  DD
E   II  EE
E   II  FF
F   G   D
F   G   E
F   G   F
F   G   DD
F   G   EE
F   G   FF
F   H   D
F   H   E
F   H   F
F   H   DD
F   H   EE
F   H   FF
F   I   D
F   I   E
F   I   F
F   I   DD
F   I   EE
F   I   FF
F   GG  D
F   GG  E
F   GG  F
F   GG  DD
F   GG  EE
F   GG  FF
F   HH  D
F   HH  E
F   HH  F
F   HH  DD
F   HH  EE
F   HH  FF
F   II  D
F   II  E
F   II  F
F   II  DD
F   II  EE
F   II  FF
DD  G   D
DD  G   E
DD  G   F
DD  G   DD
DD  G   EE
DD  G   FF
DD  H   D
DD  H   E
DD  H   F
DD  H   DD
DD  H   EE
DD  H   FF
DD  I   D
DD  I   E
DD  I   F
DD  I   DD
DD  I   EE
DD  I   FF
DD  GG  D
DD  GG  E
DD  GG  F
DD  GG  DD
DD  GG  EE
DD  GG  FF
DD  HH  D
DD  HH  E
DD  HH  F
DD  HH  DD
DD  HH  EE
DD  HH  FF
DD  II  D
DD  II  E
DD  II  F
DD  II  DD
DD  II  EE
DD  II  FF
EE  G   D
EE  G   E
EE  G   F
EE  G   DD
EE  G   EE
EE  G   FF
EE  H   D
EE  H   E
EE  H   F
EE  H   DD
EE  H   EE
EE  H   FF
EE  I   D
EE  I   E
EE  I   F
EE  I   DD
EE  I   EE
EE  I   FF
EE  GG  D
EE  GG  E
EE  GG  F
EE  GG  DD
EE  GG  EE
EE  GG  FF
EE  HH  D
EE  HH  E
EE  HH  F
EE  HH  DD
EE  HH  EE
EE  HH  FF
EE  II  D
EE  II  E
EE  II  F
EE  II  DD
EE  II  EE
EE  II  FF
FF  G   D
FF  G   E
FF  G   F
FF  G   DD
FF  G   EE
FF  G   FF
FF  H   D
FF  H   E
FF  H   F
FF  H   DD
FF  H   EE
FF  H   FF
FF  I   D
FF  I   E
FF  I   F
FF  I   DD
FF  I   EE
FF  I   FF
FF  GG  D
FF  GG  E
FF  GG  F
FF  GG  DD
FF  GG  EE
FF  GG  FF
FF  HH  D
FF  HH  E
FF  HH  F
FF  HH  DD
FF  HH  EE
FF  HH  FF
FF  II  D
FF  II  E
FF  II  F
FF  II  DD
FF  II  EE
FF  II  FF