获取所有可能的子集 - 维持秩序

Question

这是一个跟进这个问题： Generate all "unique" subsets of a set (not a powerset)

我的问题是一样的，但是我觉得可能是一个更优化的解决方案时，在新的子集项目的顺序和跨子集需要保留。

例子：

[1, 2, 3] 

会导致：

[[1], [2], [3]] 
[[1, 2], [3]] 
[[1], [2, 3]] 
[[1, 2, 3]] 

Answer 1

我已经already answered this question for Python，所以我很快移植我的解决方案到红宝石：

def spannings(lst) 
    return enum_for(:spannings, lst) unless block_given? 

    yield [lst] 
    (1...lst.size).each do |i| 
    spannings(lst[i..-1]) do |rest| 
     yield [lst[0,i]] + rest 
    end 
    end 
end 

p spannings([1,2,3,4]).to_a 

看到我的其他答案的如何以及为什么这个工程的完整说明。

Answer 2

如果我理解正确的话，你要插入 “分隔符” 到一个列表，对其分区。以你的榜样，并使用|字符表示分隔符，

1 2 3 
1 2|3 
1|2 3 
1|2|3 

是你想要的解决方案。

在列表中（我称之为列表而不是集合，因为您需要保存订单）n元素，有n-1潜在的分隔符位置。在上面的例子中，有两个位置。在每个位置，分隔符可能存在也可能不存在。

您可以使用从0到2^(n-1) - 1的数字的二进制表示来列出分隔符的所有可能排列。在你的例子中，这将是0..3的数字。

0: 00 
1: 01 
2: 10 
3: 11