如何生成具有限制的子集列表?

下面的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";
  }
}

如果生成所有子集,最终将生成2 ⁿ 长度列表的子集 n .一种常见的方法是迭代所有的数字 我 从0到2 ⁿ -1并使用设置的位 我 确定哪些项目在 我 TH子集。这是因为在任何特定的子集中都存在或不存在任何项,所以通过迭代 n 在2中迭代的位 ⁿ 子集。

例如,要生成(1、2、3)的子集,您需要迭代数字0到7:

0=000 _乙 →()
1=001 _乙 (1)
2=010 _乙 (2)
3=011 _乙 (1, 2)
4=100 _乙 (3)
5=101 _乙 (1, 3)
6=110 _乙
乙 →(1、2、3)

在您的问题中,您可以生成每个子集及其补集,以获得互斥的子集对。当您这样做时,每对都会重复,因此您只需要重复最多2次 ^{n - 1} -1然后停止。

1=001 _乙 →(1)+(2,3)
_乙 →(2)+(1,3)
3=011 _乙 →(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)

有点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,以及结果列表返回h,l1,l2和l1,h,l2中的每个l1,l2元素,也要递归地运行算法。

我的建议是…

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

重复这个数量的组合。

在每个组合中,复制循环计数(x),然后通过哈希表项开始一个内部循环。

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

如果您担心组合的数量可能会溢出整数类型,那么这个问题是可以避免的。使用一个数组,其中每个项(每个hashmap键一个)从零开始,通过组合“count”将每个数组项视为一个数字(因此整个数组表示组合数),但每个“digit”具有不同的基数(对应的计数)。也就是说,要“递增”数组,首先递增项0。如果它溢出(等于其计数),则将其设置为零并增加下一个数组项。重复溢出检查,直到溢出继续超过数组末尾,您就完成了。

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