3

我有一个任意长度的数字列表列表。

例如：

a = [[3,17,19,4],[4,18,10,1],[11,15,13],[7,9,12,16]]

嵌套级别仅限于此深度。

我想找到所有列表，其第一个元素来自第一个内部列表，其第二个元素来自第二个内部列表，依此类推，这样这个新列表的元素都在增加。

根据给定的示例，[4,10,11,12] 就是这样一个列表。

我正在苦苦挣扎，我希望解决方案是通用的，与有多少内部列表无关。

如果保证我有四个内部列表，我可以天真地编写代码：

for w in a[0]:
    for x in a[1]:
        for y in a[2]:
            for z in a[3]:
                if w < x < y < z:
                    print [w,x,y,z]

但是如果我添加第五个内部列表，或者删除上面的第四个内部列表，我就不走运了。

无论主列表中有多少内部列表，如何生成所有单调递增的“子列表”？

4

2 回答 2

3 
def combine(lists, peak=None):
  if not lists:
    yield []
  else:
    for i in lists[0]:
      if peak is None or i > peak:
        for tail in combine(lists[1:], i):
          yield [ i ] + tail

for x in combine([[3,17,19,4],[4,18,10,1],[11,15,13],[7,9,12,16]]): print x

[3, 4, 11, 12]
[3, 4, 11, 16]
[3, 4, 15, 16]
[3, 4, 13, 16]
[3, 10, 11, 12]
[3, 10, 11, 16]
[3, 10, 15, 16]
[3, 10, 13, 16]
[4, 10, 11, 12]
[4, 10, 11, 16]
[4, 10, 15, 16]
[4, 10, 13, 16]
于 2013-05-08T21:23:09.520 回答
1

如果性能不是问题，您可以使用itertools.product并循环所有可能性，例如

from itertools import product

def is_increasing(seq):
    return all(x < y for x,y in zip(seq[:-1], seq[1:]))

之后

>>> a = [[3,17,19,4],[4,18,10,1],[11,15,13],[7,9,12,16]]
>>> [k for k in product(*a) if is_increasing(k)]
[(3, 4, 11, 12), (3, 4, 11, 16), (3, 4, 15, 16), 
(3, 4, 13, 16), (3, 10, 11, 12), (3, 10, 11, 16), 
(3, 10, 15, 16), (3, 10, 13, 16), (4, 10, 11, 12), 
(4, 10, 11, 16), (4, 10, 15, 16), (4, 10, 13, 16)]

[关于性能的评论不是因为itertools.product它本身很慢，只是如果你这样做，你必须搜索每一种可能性，即使你可以用更智能的算法更早地排除它。]

于 2013-05-08T21:20:11.423 回答