1

我正在努力编写一种算法来将数组转换为该数组的所有可能排列，但它们必须是内联/连续的。下面的例子：

大批：

['a', 'b', 'c', 'd', 'e', 'f']

结果将是：

[['a'], ['b', 'c', 'd', 'e', 'f']]
[['a', 'b'], ['c', 'd', 'e', 'f']]
[['a', 'b'], ['c', 'd'], ['e', 'f']]
...

Array#permutations创建排列，但它们不是按顺序排列的。

任何帮助表示赞赏。

4

3 回答 3

3 
a = ['a', 'b', 'c', 'd', 'e', 'f']
(0...a.length)
.flat_map{|i| (1...a.length).to_a.combination(i).to_a}
.map{|cut| i = -1; a.slice_before{cut.include?(i +=1)}.to_a}
于 2013-07-19T04:00:06.790 回答
2

据我了解您的问题（这与其他人的理解不同），您希望数组的每个可能的分组（分区）数组的各个元素（字符）保持其顺序（总是'a'，然后'b'，然后'c'， ... 'f'）。我认为这是获取每个分区大小的有序列表集的问题。

也就是说，我首先将您的三个示例分区表示为：

[[1, 5],
 [2, 4],
 [2, 2, 2],
 ...]

所以我首先生成：

[[6], [1, 5], [2, 4], [3, 3] ...]

然后用它来生成最终结果。

我生成尺寸的方式非常低效。这是首先想到的，它适用于您的阵列，但如果需要处理更大的阵列，则需要更好的算法。（sawa 现在提供了一种更短、更有效的解决方案。）

def sizes(n)
  (1..n).each_with_object([]) do |i, sizes|
    sizes.concat (1..n).to_a.repeated_permutation(i).select{|a| a.reduce(:+) == n}
  end
end

def partitions_of(a)
  sizes(a.size).each_with_object([]) do |sizes, results|
    dup = a.dup
    results << sizes.each_with_object([]) do |size, result|
      result << dup.shift(size)
    end
  end
end

使用你的数组，这个：

partitions_of(['a', 'b', 'c', 'd', 'e', 'f'])

产生这个：

[[["a", "b", "c", "d", "e", "f"]],
 [["a"], ["b", "c", "d", "e", "f"]],
 [["a", "b"], ["c", "d", "e", "f"]],
 [["a", "b", "c"], ["d", "e", "f"]],
 [["a", "b", "c", "d"], ["e", "f"]],
 [["a", "b", "c", "d", "e"], ["f"]],
 [["a"], ["b"], ["c", "d", "e", "f"]],
 [["a"], ["b", "c"], ["d", "e", "f"]],
 [["a"], ["b", "c", "d"], ["e", "f"]],
 [["a"], ["b", "c", "d", "e"], ["f"]],
 [["a", "b"], ["c"], ["d", "e", "f"]],
 [["a", "b"], ["c", "d"], ["e", "f"]],
 [["a", "b"], ["c", "d", "e"], ["f"]],
 [["a", "b", "c"], ["d"], ["e", "f"]],
 [["a", "b", "c"], ["d", "e"], ["f"]],
 [["a", "b", "c", "d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d", "e", "f"]],
 [["a"], ["b"], ["c", "d"], ["e", "f"]],
 [["a"], ["b"], ["c", "d", "e"], ["f"]],
 [["a"], ["b", "c"], ["d"], ["e", "f"]],
 [["a"], ["b", "c"], ["d", "e"], ["f"]],
 [["a"], ["b", "c", "d"], ["e"], ["f"]],
 [["a", "b"], ["c"], ["d"], ["e", "f"]],
 [["a", "b"], ["c"], ["d", "e"], ["f"]],
 [["a", "b"], ["c", "d"], ["e"], ["f"]],
 [["a", "b", "c"], ["d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d"], ["e", "f"]],
 [["a"], ["b"], ["c"], ["d", "e"], ["f"]],
 [["a"], ["b"], ["c", "d"], ["e"], ["f"]],
 [["a"], ["b", "c"], ["d"], ["e"], ["f"]],
 [["a", "b"], ["c"], ["d"], ["e"], ["f"]],
 [["a"], ["b"], ["c"], ["d"], ["e"], ["f"]]]

如果我理解正确，这正是您所追求的。

于 2013-07-19T00:19:11.923 回答
1

如果您想要数组的所有可能排列的所有可能组合，则生成排列，然后生成它们的切片：

array = %w(a b c d e f)
r = array.permutation(array.length).map {|perm|
  perm.length.times.map {|i| perm.each_slice(i+1).to_a }
}.flatten(1)

这将生成输入数组的每个可能排列的每个可能的分组。不过，我不太确定这就是你要找的东西。

于 2013-07-19T01:13:14.023 回答