子元组用于元组数据类型。

Question

我希望您能翻译以下内容：

(('A',), ('B',), ('C',), ('D',))
(('A',), ('B',), ('C','D'))
(('A',), ('B','C'), ('D',))
(('A',), ('B','C','D'))
(('A','B'), ('C',), ('D',))
(('A','B'), ('C','D'))
(('A','B','C'), ('D',))
(('A','B','C','D'),)

当调用sub_combinations(('A', 'B', 'C', 'D'))时

这里是我的尝试，但它没有起作用：

def sub_combinations(segment):
   for i in range(1, len(segment)):
      for j in sub_combinations(segment[i:]):
         yield segment[:i]+j 
      yield segment 

但我认为我正在走上正确的轨道。

此外，我希望有第二个参数名为limit，它可以限制子元组的大小。例如，sub_combinations(('A', 'B', 'C', 'D'), 2)将给出：

(('A',), ('B',), ('C',), ('D',))
(('A',), ('B',), ('C','D'))
(('A',), ('B','C'), ('D',))
(('A','B'), ('C',), ('D',))
(('A','B'), ('C','D'))

我正在使用Python 3。

- Baz

---

你有研究过itertools吗？另外，请发布您当前函数的实际输出。 - jonrsharpe

你想要的不是“组合”，而是“集合划分”。 - interjay

@interjay 已相应地更改问题名称。 - Baz

其实我认为我错了。集合划分应该包括例如 "{{A,C},{B,D}}"，而在你的例子中，所有子集都包含连续的元素。我不确定这应该被称为什么。 - interjay

@interjay：子元组可能是更好的措辞 ;) - masu

@SándorKazi 这是Python打印单元素元组的方式，否则它只会成为一个带括号的字符串。 - tobias_k

Answer 1

处理基本情况 - 当 segment 为空时：

def sub_combinations(segment, size=0):
    if segment == ():
        yield ()
        return
    stop = min(size or len(segment), len(segment))
    for i in range(1, stop + 1):
        for j in sub_combinations(segment[i:], size):
            yield (segment[:i],) + j

使用示例：

>>> for x in sub_combinations(('A', 'B', 'C', 'D')):
...     print(x)
...
(('A',), ('B',), ('C',), ('D',))
(('A',), ('B',), ('C', 'D'))
(('A',), ('B', 'C'), ('D',))
(('A',), ('B', 'C', 'D'))
(('A', 'B'), ('C',), ('D',))
(('A', 'B'), ('C', 'D'))
(('A', 'B', 'C'), ('D',))
(('A', 'B', 'C', 'D'),)

---

>>> for x in sub_combinations(('A', 'B', 'C', 'D'), 2):
...     print(x)
...
(('A',), ('B',), ('C',), ('D',))
(('A',), ('B',), ('C', 'D'))
(('A',), ('B', 'C'), ('D',))
(('A', 'B'), ('C',), ('D',))
(('A', 'B'), ('C', 'D'))

- falsetru

Answer 2

如果您可以接受使用列表而不是元组（或者不怕稍后进行转换），则可以使用以下方法：

def subtuples(t):
  for i in range(1<< (len(t)-1)):
    result = [ [ t[0] ] ]
    for j in range(len(t)-1):
      if (1<<j) & i:
        result[-1].append(t[j+1])
      else:
        result.append([ t[j+1] ])
    yield result

for x in subtuples(('a', 'b', 'c', 'd')):
  print(x)

- Alfe

---

其实，我更喜欢falsetru的递归算法，但也许在某些特定限制下，我的算法效果更好。 - Alfe

关于递归的典型问题，大多数涉及堆栈深度、内存消耗，可能也包括性能。但正如我所说，我更喜欢你的方法，它更加优雅。我刚刚完成了我的方法，现在不想完全删除它。在特定情况下，它可能更好用。 - Alfe

我在CPython 3.4b3、CPython 2.7.6中运行了这个程序。递归版本表现更好（大约快2倍）。在PyPy中，你的版本运行得非常快。 - falsetru

是的，PyPy 是个不错的东西。就像在练习使用刀具一段时间后拿起一把机枪一样。 - Alfe

根据这个链接，看起来PyPy仍然不喜欢递归使用生成器 ;) - falsetru