没有多重集合的k-组合的通用解决方案？

huangapple
go评论77阅读模式
英文:

No general solution to k-combination of multiset?

问题

以下是您要翻译的内容：

The problem to solve

解决可能包含重复项的 k-组合问题，并仅返回唯一的组合。

例如，输入为 [0,1,2,2,4]，k = 2，结果为：

{(0, 1), (2, 4), (1, 2), (0, 4), (1, 4), (0, 2), (2, 2)}

The solution I can think of

我能想到的唯一通用解决方案是使用 set 或 map 来提取唯一结果。

例如，在Python中：

  1. from itertools import combinations
  2. print(set(combinations([0, 1, 2, 2, 4], 2)))

Questions

  • 是否有一种通用解决方案可以在不使用 set/map 进行过滤的情况下完成此操作。

我可以生成按顺序的唯一项组合（参考：https://stackoverflow.com/a/76048486），但如果存在重复项，则会有重复的组合。

我阅读了这个：https://math.stackexchange.com/a/554237，似乎它说没有一种通用解决方案可以获取所有唯一的组合，尽管有一种获得唯一组合数量的公式。

但是，我不确定。

@Update - Summary & tips

  • 根据答案，可以通过迭代和递归两种方式来完成此操作。
  • 从python翻译为go时：
    • 在Python中的yield需要在Go中使用chan，或者需要返回所有组合（对于大量输入可能很大）。
    • Python中的else用于for和while循环，当使用break时在Go中会省略。
    • Python中的列表切片会创建一个副本（或引用？），而在Go中切片一个切片将重用相同的底层数组（因此在Go中，如果要复制的切片稍后将被修改，而且不希望在副本中出现该更改，则应将其复制/附加到新切片中）。
英文:

The problem to solve

Solve k-combination whose input may contain repeated items, and return only unique combinations.

e.g input is [0,1,2,2,4], k = 2, the result is:
> {(0, 1), (2, 4), (1, 2), (0, 4), (1, 4), (0, 2), (2, 2)}

The solution I can think of

The only general solution I can think is to use a set or map to extract unique results.

e.g with python
<!-- language: python -->

  1. from itertools import combinations
  2. print (set(combinations([0, 1, 2, 2, 4], 2)))

Questions

  • Is there a general solution to do this, without using a set/map for filtering.

I can generate combinations of unique items, in order (refer: https://stackoverflow.com/a/76048486), but if there are repeated items, then there will be repeated combinations.

I've read this: https://math.stackexchange.com/a/554237 , seems it says there is no general solution to get all unique combinations, though there do have a formula to get count of unique combinations.

But, I'm not sure.

@Update - Summary & tips

  • According to the answers, there are ways both via iteration & recursion to do this.
  • When translating from python to go:
    • yield in python, need chan in go, or u need return all combinations (which can be huge for large input).
    • python's else for for and while is omitted when break.
    • list slicing in python will make a copy (of reference ?), while slicing a go slice will reuse the same underlying array, (so in go, if the slice being copied will be modified later, and u don't want that change in the copy, then u should copy/append it into a new slice).

答案1

得分: 3

以下是提供的Python代码的中文翻译：

这是一个按词典顺序优化简单性而不是速度的非递归组合枚举器。Knuth的《计算机程序设计艺术》几乎肯定有一个速度优化的版本。

  1. def combinations(a, k):
  2.     a = sorted(a)
  3.     while True:
  4.         yield a[:k]
  5.         for i in range(k - 1, -1, -1):
  6.             # a[i + 1 :] 已排序。对 a[i:] 进行排序。
  7.             x = a[i]
  8.             j = i + 1
  9.             while j < len(a):
  10.                 if x < a[j]:
  11.                     break
  12.                 a[j - 1] = a[j]
  13.                 j += 1
  14.             a[j - 1] = x
  15.             # a[j] 是 x 之后的下一个最大元素。如果后面有足够多的元素，将它们旋转到适当位置。
  16.             if j + (k - i) <= len(a):
  17.                 rotate(a, i, j, j + (k - i))
  18.                 break
  19.         else:
  20.             break
  22. def rotate(a, i, j, k):
  23.     reverse(a, i, j)
  24.     reverse(a, j, k)
  25.     reverse(a, i, k)
  27. def reverse(a, i, k):
  28.     for j in range((k - i) // 2):
  29.         a[i + j], a[(k - 1) - j] = a[(k - 1) - j], a[i + j]
  31. print(*combinations([0, 1, 2, 2, 4], 2))
  32. print(*combinations([0, 1, 2, 2, 4], 3))
  33. print(*combinations([0, 0, 0, 1, 1, 1], 3))

输出：

  1. [0, 1] [0, 2] [0, 4] [1, 2] [1, 4] [2, 2] [2, 4]
  2. [0, 1, 2] [0, 1, 4] [0, 2, 2] [0, 2, 4] [1, 2, 2] [1, 2, 4] [2, 2, 4]
  3. [0, 0, 0] [0, 0, 1] [0, 1, 1] [1, 1, 1]
英文:

Here’s a non-recursive enumerator for combinations in lexicographic order, optimized for simplicity over speed. Knuth’s The Art of Computer Programming almost certainly has a speed-optimized version.

  1. def combinations(a, k):
  2.     a = sorted(a)
  3.     while True:
  4.         yield a[:k]
  5.         for i in range(k - 1, -1, -1):
  6.             # a[i + 1 :] is sorted. Sort a[i:].
  7.             x = a[i]
  8.             j = i + 1
  9.             while j &lt; len(a):
  10.                 if x &lt; a[j]:
  11.                     break
  12.                 a[j - 1] = a[j]
  13.                 j += 1
  14.             a[j - 1] = x
  15.             # a[j] is the next greatest element after x. If there are enough
  16.             # elements after it, rotate them into position.
  17.             if j + (k - i) &lt;= len(a):
  18.                 rotate(a, i, j, j + (k - i))
  19.                 break
  20.         else:
  21.             break
  24. def rotate(a, i, j, k):
  25.     reverse(a, i, j)
  26.     reverse(a, j, k)
  27.     reverse(a, i, k)
  30. def reverse(a, i, k):
  31.     for j in range((k - i) // 2):
  32.         a[i + j], a[(k - 1) - j] = a[(k - 1) - j], a[i + j]
  35. print(*combinations([0, 1, 2, 2, 4], 2))
  36. print(*combinations([0, 1, 2, 2, 4], 3))
  37. print(*combinations([0, 0, 0, 1, 1, 1], 3))

Output:

  1. [0, 1] [0, 2] [0, 4] [1, 2] [1, 4] [2, 2] [2, 4]
  2. [0, 1, 2] [0, 1, 4] [0, 2, 2] [0, 2, 4] [1, 2, 2] [1, 2, 4] [2, 2, 4]
  3. [0, 0, 0] [0, 0, 1] [0, 1, 1] [1, 1, 1]

答案2

得分: 1

以下是使用Python生成这些内容的代码。

我正在使用迭代器。将其转化为另一种语言可能是翻译这个过程中最困难的部分。

  1. def unique_multisets(multiset, k):
  2.     # 查找每个项目的重复次数。
  3.     count = {}
  4.     for x in multiset:
  5.         count[x] = 1 + count.get(x, 0)
  7.     # 将其转化为（值，重复次数）对。reverse是因为我们稍后会在生成多重集时将其反转。
  8.     pairs = list(reversed(count.items()))
  10.     # 计算累积总数。
  11.     total = 0
  12.     totals = []
  13.     for p in pairs:
  14.         total += p[1]
  15.         totals.append(total)
  17.     def recurse(partial, idx):
  18.         if k == len(partial):
  19.             yield partial
  20.         elif idx < 0 or totals[idx] < k - len(partial):
  21.             pass  # 无法生成组合。
  22.         else:
  23.             (value, repeat) = pairs[idx]
  24.             max_used = min(repeat, k - len(partial))
  25.             for i in range(1 + max_used):
  26.                 partial.append(value)
  27.             for i in range(1 + max_used):
  28.                 partial.pop()
  29.                 yield from recurse(partial, idx - 1)
  31.     yield from recurse([], len(pairs) - 1)
  33. for x in unique_multisets([0, 1, 2, 2, 4], 2):
  34.     print(x)

希望这可以帮助您理解这段代码。

英文:

Here is code that generates these one at a time in Python.

I'm using iterators. Translating away from that would be the hardest part of translating this to another language.

  1. def unique_multisets (multiset, k):
  2.     # Find the repetition of each item.
  3.     count = {}
  4.     for x in multiset:
  5.         count[x] = 1 + count.get(x, 0)
  7.     # Turn this into (value, count) pairs.  The reversed is
  8.     # because we will reverse it later in generating the multisets.
  9.     pairs = list(reversed(count.items()))
  11.     # Calculate a running total.
  12.     total = 0
  13.     totals = []
  14.     for p in pairs:
  15.         total += p[1]
  16.         totals.append(total)
  18.     def recurse (partial, idx):
  19.         if k == len(partial):
  20.             yield partial
  21.         elif idx &lt; 0 or totals[idx] &lt; k - len(partial):
  22.             pass # Can&#39;t make combinations.
  23.         else:
  24.             (value, repeat) = pairs[idx]
  25.             max_used = min(repeat, k - len(partial))
  26.             for i in range(1 + max_used):
  27.                 partial.append(value)
  28.             for i in range(1 + max_used):
  29.                 partial.pop()
  30.                 yield from recurse(partial, idx - 1)
  32.     yield from recurse([], len(pairs)-1)
  34. for x in unique_multisets([0, 1, 2, 2, 4], 2):
  35.     print(x)

答案3

得分: 1

以下是我为这个任务开发的一个算法：

  1. def multiset_combinations(v, m):
  2.     
  3.     v = sorted(v)
  4.     f = [0]
  5.     j = 0
  7.     # 填充f，一个扩展索引的列表。例如，
  8.     #
  9.     #    v = [2, 2, 33, 33, 33, 40]
  10.     #
  11.     # f将是：
  12.     #
  13.     #    [0, 0, 1, 1, 1, 2]
  14.     
  15.     for i in range(1, len(v)):
  16.         if v[i] != v[i - 1]:
  17.             j += 1
  19.         f.append(j)
  21.     v = list(set(v))
  22.     r = [0] * m
  23.     n = len(v)
  24.     
  25.     z   = f[:m]
  26.     idx = [0] * n
  27.     p   = len(f) - m
  28.     
  29.     last = f[-m:]
  30.     last[-1] += 1
  31.     
  32.     # 找到每个索引的第一个出现。例如，对于上面的示例，idx将是：
  33.     #
  34.     #   [0, 2, 5]
  35.     
  36.     for i in range(n):
  37.         idx[i] = f.index(i)
  38.     
  39.     # 主要算法
  41.     while True:
  42.         while z[-1] < n:
  43.             for j in range(m):
  44.                 r[j] = v[z[j]]
  46.             z[-1] += 1
  47.             yield r.copy()
  49.         if z == last:
  50.             break
  51.         
  52.         for i in range(m - 2, -1, -1):
  53.             if z[i] != f
    :
  54.                 z[i] += 1
  55.                 
  56.                 for j, k in zip(range(i + 1, m),
  57.                                 range(idx[z[i]] + 1, idx[z[i]] + m)):
  58.                     z[j] = f[k]
  59.                 
  60.                 break

调用它：

  1. print(*multiset_combination([0, 1, 2, 2, 4], 2))
  2. #> [0, 1] [0, 2] [0, 4] [1, 2] [1, 4] [2, 2] [2, 4]
  4. print(*multiset_combination([0, 1, 2, 2, 4], 3))
  5. #> [0, 1, 2] [0, 1, 4] [0, 2, 2] [0, 2, 4] [1, 2, 2] [1, 2, 4] [2, 2, 4]
  7. print(*multiset_combination([0, 0, 0, 1, 1, 1], 3))
  8. #> [0, 0, 0] [0, 0, 1] [0, 1, 1] [1, 1, 1]

它也相当高效。它可以在不到一秒的时间内生成753564：

  1. v1 = [1,
  2.       2, 2,
  3.       3, 3, 3,
  4.       4, 4, 4, 4,
  5.       5, 5, 5, 5, 5,
  6.       6,
  7.       7, 7,
  8.       8, 8, 8,
  9.       9, 9, 9, 9,
  10.       10, 10, 10, 10, 10,
  11.       11,
  12.       12, 12,
  13.       13, 13, 13,
  14.       14, 14, 14, 14,
  15.       15, 15, 15, 15, 15]
  16.       
  17. def get_time(v, m):
  18.     t1 = time.time()
  19.     list(multiset_combinations(v, m))
  20.     t2 = time.time()
  21.     return t2 - t1
  22.     
  23. get_time(v1, 10)
  24. #> 0.8702290058135986
英文:

Below is an algorithm I developed some time back for this task:

  1. def multiset_combinations(v, m):
  2.     
  3.     v = sorted(v)
  4.     f = [0]
  5.     j = 0
  7.     # Populating f, a list of expanded indices. E.g. For
  8.     #
  9.     #    v = [2, 2, 33, 33, 33, 40]
  10.     #
  11.     # f would be:
  12.     #
  13.     #    [0, 0, 1, 1, 1, 2]
  14.     
  15.     for i in range(1, len(v)):
  16.         if v[i] != v[i - 1]:
  17.             j += 1
  19.         f.append(j)
  21.     v = list(set(v))
  22.     r = [0] * m
  23.     n = len(v)
  24.     
  25.     z   = f[:m]
  26.     idx = [0] * n
  27.     p   = len(f) - m
  28.     
  29.     last = f[-m:]
  30.     last[-1] += 1
  31.     
  32.     # Find the first occurence of each index. E.g. For the
  33.     # same example above, idx would be:
  34.     #
  35.     #   [0, 2, 5]
  36.     
  37.     for i in range(n):
  38.         idx[i] = f.index(i)
  39.     
  40.     # The main algorithm
  42.     while True:
  43.         while z[-1] &lt; n:
  44.             for j in range(m):
  45.                 r[j] = v[z[j]]
  47.             z[-1] += 1
  48.             yield r.copy()
  50.         if z == last:
  51.             break
  52.         
  53.         for i in range(m - 2, -1, -1):
  54.             if z[i] != f
    :
  55.                 z[i] += 1
  56.                 
  57.                 for j, k in zip(range(i + 1, m),
  58.                                 range(idx[z[i]] + 1, idx[z[i]] + m)):
  59.                     z[j] = f[k]
  60.                 
  61.                 break

Calling it:

  1. print(*multiset_combination([0, 1, 2, 2, 4], 2))
  2. #&gt; [0, 1] [0, 2] [0, 4] [1, 2] [1, 4] [2, 2] [2, 4]
  4. print(*multiset_combination([0, 1, 2, 2, 4], 3))
  5. #&gt; [0, 1, 2] [0, 1, 4] [0, 2, 2] [0, 2, 4] [1, 2, 2] [1, 2, 4] [2, 2, 4]
  7. print(*multiset_combination([0, 0, 0, 1, 1, 1], 3))
  8. #&gt; [0, 0, 0] [0, 0, 1] [0, 1, 1] [1, 1, 1]

It is pretty efficient as well. It can generate 753564 in just under a second:

  1. v1 = [1,
  2.       2, 2,
  3.       3, 3, 3,
  4.       4, 4, 4, 4,
  5.       5, 5, 5, 5, 5,
  6.       6,
  7.       7, 7,
  8.       8, 8, 8,
  9.       9, 9, 9, 9,
  10.       10, 10, 10, 10, 10,
  11.       11,
  12.       12, 12,
  13.       13, 13, 13,
  14.       14, 14, 14, 14,
  15.       15, 15, 15, 15, 15]
  16.       
  17. def get_time(v, m):
  18.     t1 = time.time()
  19.     list(multiset_combinations(v, m))
  20.     t2 = time.time()
  21.     return t2 - t1
  22.     
  23. get_time(v1, 10)
  24. #&gt; 0.8702290058135986

huangapple
  • 本文由 发表于 2023年4月20日 05:17:29
  • 转载请务必保留本文链接：https://go.coder-hub.com/76058880.html
  • algorithm
  • combinations
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定