如何获取字符串的所有子序列组合（在Java中，或C++等）

algorithm java c++

2022-09-02 04:58:04

假设我有一个字符串“12345”，我应该获取此字符串的所有子序列组合，例如：

--> 1 2 3 4 5
--> 12 13 14 15 23 24 25 34 35 45
--> 123 124 125 234 235 345
--> 1234 1235 1245 1345 2345
--> 12345

请注意，我将它们分组为不同数量的字符，但没有更改其顺序。我需要一个方法/函数来做到这一点。

答案 1

你想要一个电源集。以下是StackOverflow上所有提到电源集或电源集的问题。

以下是python中的基本实现：

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield [s[j] for j in range(n) if (masks[j] & i)]


if __name__ == '__main__':
    for elem in powerset([1,2,3,4,5]):
        print elem

这是它的输出：

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

请注意，它的第一个结果是空集。如果要跳过空集，请将迭代从此更改为此。for i in xrange(2**n):for i in xrange(1, 2**n):

下面是适合生成字符串输出的代码：

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield "".join([str(s[j]) for j in range(n) if (masks[j] & i)])

编辑 2009-10-24

好吧，我看到你偏爱Java中的实现。我不懂Java，所以我会在中途遇到你，给你用C#编写的代码：

    static public IEnumerable<IList<T>> powerset<T>(IList<T> s)
    {
        int n = s.Count;
        int[] masks = new int[n];
        for (int i = 0; i < n; i++)
            masks[i] = (1 << i);
        for (int i = 0; i < (1 << n); i++)
        {
            List<T> newList = new List<T>(n);
            for (int j = 0; j < n; j++)
                if ((masks[j] & i) != 0)
                    newList.Add(s[j]);
            yield return newList;
        }
    }

答案 2

生成一组大小为 N 的子集的最简单算法是使用 N 位考虑所有二进制数。数字中的每个位置表示集合中的一个元素。如果数字中的位为 1，则相应的 set 元素位于子集中，否则该元素不在子集中。由于数字中的位是有序的，因此这将保留原始集合的顺序。

引用：

"有效地枚举集合的子集“;Loughry， Hemert and Schoofs
"生成子集“;石溪算法存储库