獲取所有可能的子集 - 維持秩序

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