Stream all unordered/shuffled unique permutation o

2019-08-20 05:50发布

I have two-level nested list like following.

[[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]

I want to generate all 8 unique permutations of this nested list, but my application absolutely needs the output to be (pseudo-)randomized and unordered. Usually, permutation strategies produce the permutations in order, but I want to be able to produce all permutations out of order.

Moreover, this MUST be done through some generator, as the nested list can be very long, and number of unique permutations can explode combinatorially.

Case in point, the following output is desired for the above list.

(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)

...as opposed to the following, which is generated by itertools.product(*some_list):

(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)

Even some solution that does exactly what itertools.product does, but generates permutations out of order will help me a lot. Any help is appreciated.

The following code illustrates my existing approach.

def perm_attempt():
    meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
    print meta_seq
    iter_count = np.prod([len(set(x)) for x in meta_seq])
    print iter_count
    print
    set_l = set()
    for _ in xrange(iter_count*10):
        l = [np.random.choice(x) for x in meta_seq]
        # print l
        set_l.add(tuple(l))
    print
    print len(set_l)
    print
    # for s in set_l:
    #     print s

3条回答
三岁会撩人
2楼-- · 2019-08-20 06:28

If memory will not be a problem, you can try the following:

permList = itertools.product(*list_of_lists)
randomPermList = numpy.random.permutation(list(permList))

This is unique and random, but will not be an iteration.

查看更多
趁早两清
3楼-- · 2019-08-20 06:47

A little cleaner than your current solution:

meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
print meta_seq
iter_count = np.prod([len(set(x)) for x in meta_seq])
print iter_count
print
set_l = set()
for _ in xrange(iter_count*100):
    choices = tuple([np.random.choice(sub_seq) for sub_seq in meta_seq])
    if not choices in set_l:
        set_l.add(choices)
        print choices
print
print len(set_l)
print
查看更多
聊天终结者
4楼-- · 2019-08-20 06:48

You can try iterating over the following generator:

def random_perm(l):
    while True:
        yield [random.choice(sublist) for sublist in l]

Sample usage:

l = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
g = random_perm(l)
for _ in range(10):
    print(next(g))

Output:

[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]

However, as others have pointed out in the comments, unless you cache the yield results in memory somehow, you can't really guarantee you won't get duplicates. You are also not guaranteed to get all 8 unique iterations in any 8 consecutive iterations.

查看更多
登录 后发表回答