1

我试图找出一种有效的算法来获取项目列表并生成所有唯一子集，这些子集是通过将列表拆分为恰好 2 个子列表而产生的。我确信有一种通用的方法可以做到这一点，但我对一个特定的案例感兴趣。我的列表将被排序，并且可以有重复的项目。

一些例子：

输入
{1,2,3}

输出
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

输入
{1,2,3,4}

输出
{{1},{2,3,4}}
{{2},{1,3,4}}
{{3},{1,2,4}}
{{4},{1,2, 3}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}

输入
{1,2,2,3}

输出
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2, 3}}
{{1,3},{2,2}}

我可以在纸上做到这一点，但我正在努力找出一种以编程方式完成它的简单方法。我只是在寻找有关如何执行此操作的快速伪代码描述，而不是任何特定的代码示例。

任何帮助表示赞赏。谢谢。

4

4 回答 4

2

如果您要生成所有子集，您最终会为长度为n的列表生成 2 n个子集。一种常见的方法是遍历从 0 到 2 n -1的所有数字i ，并使用在i中设置的位来确定哪些项目在第i个子集中。这是有效的，因为任何项目要么存在或不存在于任何特定子集中，因此通过遍历n位的所有组合，您可以遍历 2 n个子集。

例如，要生成 (1, 2, 3) 的子集，您将遍历数字 0 到 7：

0 = 000 b → ()
1 = 001 b → (1)
2 = 010 b → (2)
3 = 011 b → (1, 2)
4 = 100 b → (3)
5 = 101 b → (1, 3 )
6 = 110 b → (2, 3)
7 = 111 b → (1, 2, 3)

在您的问题中，您可以生成每个子集及其补集，以获得您的一对互斥子集。当你这样做时，每一对都会重复，所以你只需要迭代到 2 n -1 - 1 然后停止。

1 = 001 b → (1) + (2, 3)
2 = 010 b → (2) + (1, 3)
3 = 011 b → (1, 2) + (3)

要处理重复项，您可以生成列表索引的子集而不是列表项的子集。与列表 (1, 2, 2, 3) 一样，生成列表 (0, 1, 2, 3) 的子集，然后将这些数字用作 (1, 2, 2, 3) 列表的索引。基本上，添加一个间接级别。

这是一些将这一切放在一起的 Python 代码。

#!/usr/bin/env python

def split_subsets(items):
    subsets = set()

    for n in xrange(1, 2 ** len(items) / 2):
        # Use ith index if ith bit of n is set.
        l_indices = [i for i in xrange(0, len(items)) if n & (1 << i) != 0]
        # Use the indices NOT present in l_indices.
        r_indices = [i for i in xrange(0, len(items)) if i not in l_indices]

        # Get the items corresponding to the indices above.
        l = tuple(items[i] for i in l_indices)
        r = tuple(items[i] for i in r_indices)

        # Swap l and r if they are reversed.
        if (len(l), l) > (len(r), r):
            l, r = r, l

        subsets.add((l, r))

    # Sort the subset pairs so the left items are in ascending order.
    return sorted(subsets, key = lambda (l, r): (len(l), l))

for l, r in split_subsets([1, 2, 2, 3]):
    print l, r

输出：

(1,) (2, 2, 3)
(2,) (1, 2, 3)
(3,) (1, 2, 2)
(1, 2) (2, 3)
(1, 3) (2, 2)
于 2009-10-05T18:43:30.753 回答
1

一点Erlang代码，问题是当你有重复元素时它会产生重复，所以结果列表仍然需要过滤......

do([E,F]) -> [{[E], [F]}];
do([H|T]) -> lists:flatten([{[H], T}] ++
                           [[{[H|L1],L2},{L1, [H|L2]}]  || {L1,L2} <- all(T)]).

filtered(L) ->
  lists:usort([case length(L1) < length(L2) of true -> {L1,L2};
                                               false -> {L2,L1} end
              || {L1,L2} <- do(L)]).

在伪代码中，这意味着：

  • 对于两个长列表 {E,F}，结果是 {{E},{F}}
  • 对于更长的列表，取第一个元素 H 和列表的其余部分 T 并返回
    • {{H},{T}}（第一个元素为单元素列表，其余为列表）
    • 还对 T 递归地运行算法，并为结果列表中的每个 {L1,L2} 元素返回 {{H,L1},{L2}} 和 {{L1},{H,L2}}
于 2009-10-05T18:59:40.690 回答
1

以下 C++ 函数完全符合您的需要，但顺序与示例中的不同：

// input contains all input number with duplicates allowed
void generate(std::vector<int> input) {
  typedef std::map<int,int> Map;
  std::map<int,int> mp;
  for (size_t i = 0; i < input.size(); ++i) {
    mp[input[i]]++;
  }

  std::vector<int> numbers;
  std::vector<int> mult;
  for (Map::iterator it = mp.begin(); it != mp.end(); ++it) {
    numbers.push_back(it->first);
    mult.push_back(it->second);
  }

  std::vector<int> cur(mult.size());
  for (;;) {
    size_t i = 0;
    while (i < cur.size() && cur[i] == mult[i]) cur[i++] = 0;
    if (i == cur.size()) break;
    cur[i]++;
    std::vector<int> list1, list2;
    for (size_t i = 0; i < cur.size(); ++i) {
      list1.insert(list1.end(), cur[i], numbers[i]);
      list2.insert(list2.end(), mult[i] - cur[i], numbers[i]);
    }
    if (list1.size() == 0 || list2.size() == 0) continue;
    if (list1 > list2) continue;
    std::cout << "{{";
    for (size_t i = 0; i < list1.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list1[i];
    }
    std::cout << "},{";
    for (size_t i = 0; i < list2.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list2[i];
    }
    std::cout << "}\n";
  }
}
于 2009-10-05T19:15:43.653 回答
0

我的建议是...

首先，计算您拥有的每个值的数量，可能在哈希表中。然后计算要考虑的组合总数 - 计数的乘积。

遍历该数量的组合。

在每个组合中，复制您的循环计数（作为 x），然后通过您的哈希表项​​开始一个内部循环。

对于每个哈希表项，使用 (x modulo count) 作为第一个列表中哈希表键的实例数。在重复内部循环之前将 x 除以计数。

如果您担心组合的数量可能会溢出您的整数类型，那么这个问题是可以避免的。使用从零开始的每个项目（每个哈希图键一个）的数组，并通过将每个数组项目视为数字的组合“计数”（因此整个数组表示组合编号），但每个“数字”都有一个不同的基数（相应的计数）。也就是说，要“增加”数组，首先增加第 0 项。如果溢出（变为等于其计数），请将其设置为零并增加下一个数组项。重复溢出检查，直到如果溢出继续超过数组的末尾，您就完成了。

我认为 sergdev 使用的方法与第二种方法非常相似，但使用的是 std::map 而不是哈希表（std::unordered_map 应该可以工作）。对于大量项目，哈希表应该更快，但不会以任何特定顺序为您提供值。但是，通过哈希表中的键的每个循环的顺序应该是一致的，除非您添加/删除键。

于 2009-10-05T20:16:37.943 回答