python：如何在不重复项目的情况下计算可迭代对象的笛卡尔积？

Question

我需要一个函数，它的功能和itertools.product差不多，但不重复项目。

举个例子：

no_repeat_product((1,2,3), (5,6))
= ((1,5), (None,6), (2,5), (None,6), ...(None,6))
no_repeat_product((1,2,3), (5,6), (7,8))
= ((1,5,7), (None,None,8), (None,6,7), (None,None,8), ...(None,None,8))

有没有什么想法？

补充说明：
我之前的表述不太准确。我是想说在连续的输出值中，不要重复相同的数字。
比如：

itertools.product((1,2,3), (4,5), (6,7) is
(1,4,6)
(1,4,7), etc  

在这里，1和4在输出中出现了两次。所以，我想在数字和前一个数字相同时，跳过写这个数字。因此，我想要的输出是：

(1,4,6)  
(None,None,7)  

当它是None时，表示它和结果中的前一个项目是一样的。

进一步补充：

我的解释还是不够清楚。
假设我有一本书的列表、章节号和页码。假设每本书的章节数相同，每个章节的页数也相同。
所以，列表是（书1，书2，书3），（章节1，章节2），（页1，页2，页3）。
现在，假设我想为每一页收集描述：
itertools.product会给我：

(book1, chap1, page1), (book1, chap1, page2)..... (book3, chap2, page3)

如果我把这些页面按顺序排列，我就不需要重复描述。所以，如果书和章节是一样的，在第二页时，我就不需要再写书名和章节名。
所以，输出应该是：

(book1, chap1, page1), (None, None, page2), ..   
(when the pages of first chapter are over..) (None, chap2, page1), (None, None, page2)......  
(when the chapters of the first book are over..)(book2, chap1, page1)..............  
(None, None, page3)  

Answer 1

这是对@ShawnChin回答的一种函数式版本，使用了一个叫做“tee”的迭代器：

from itertools import product,tee,izip
def product_without_repeats(*seq):
    previter,curriter = tee(product(*seq))
    try:
        yield next(curriter)
    except StopIteration:
        pass
    else:
        for prev,curr in izip(previter,curriter):
            yield tuple(y if x!=y else None for x,y in izip(prev,curr))

Answer 2

def no_repeat_product(*seq):
    def no_repeat(x, known):
        if x in known:
            return None
        else:
            known.add(x)
            return x

    known = set()
    for vals in itertools.product(*seq):
        yield tuple(no_repeat(x, known) for x in vals)

这个不会返回之前已经出现过的任何值。这是你想要的吗？

如果你只是想限制在之前的结果中出现过的值重复，可以这样做：

def no_repeat_product(*seq):
    prev = None
    for vals in itertools.product(*seq):
        if prev is None:
            yield vals
        else:
            yield tuple((x if x != y else None) for x, y in zip(vals, prev))
        prev = vals

Answer 3

根据你提到的评论“因为 (None,None,8) 不会连续出现”，我猜测你只是想把那些在输出中紧接着前面出现的元素变成 None。

def no_repeat_product(*seq):
    previous = (None,)*len(seq)
    for vals in itertools.product(*seq):
        out = list(vals)
        for i,x in enumerate(out):
            if previous[i] == x:
                out[i] = None
        previous = vals
        yield(tuple(out))   

或者，如果你更喜欢一种更紧凑和高效（但可读性差一点）的版本：

def no_repeat_product(*seq):
    previous = (None,)*len(seq)
    for vals in itertools.product(*seq):
        out = tuple((y,None)[x==y] for x,y in itertools.izip(previous, vals))
        previous = vals
        yield(out)       

这两种方法做的事情是一样的，都会产生以下结果：

for x in no_repeat_product((1,2,3), (5,6), (7,8)): 
    print x 

输出：

(1, 5, 7)
(None, None, 8)
(None, 6, 7)
(None, None, 8)
(2, 5, 7)
(None, None, 8)
(None, 6, 7)
(None, None, 8)
(3, 5, 7)
(None, None, 8)
(None, 6, 7)
(None, None, 8)

举个例子，结合你更新后的问题：

books = ("Book 1", "Book 2")
chapters = ("Chapter 1", "Chapter 2")
pages = ("Page 1", "Page 2", "Page 3")

s1 = max(map(len, books)) + 2  # size of col 1
s2 = max(map(len, chapters)) + 2  # size of col 2
x = lambda s, L: (s, "")[s == None].ljust(L)  # Left justify, handle None

for book, chapter, page in no_repeat_product(books, chapters, pages):
    print x(book, s1), x(chapter, s2), page

这样你就得到了：

Book 1   Chapter 1   Page 1
                     Page 2
                     Page 3
         Chapter 2   Page 1
                     Page 2
                     Page 3
Book 2   Chapter 1   Page 1
                     Page 2
                     Page 3
         Chapter 2   Page 1
                     Page 2
                     Page 3