如何在Python中将列表拆分为没有重复元素的子集

发布于 2024-12-16 13:09:21 字数 414 浏览 0 评论 0原文

我需要的代码接受一个列表(最多 n=31)并返回 n=3 的所有可能子集,而没有任何两个元素在同一子集中重复两次(想想每次都与新人以 3 人为一组组队的人):

list=[1,2,3,4,5,6,7,8,9]

并且返回

[1,2,3][4,5,6][7,8,9]

[1,4,7][2,3,8][3,6,9]

[1,6,8][2,4,9][3,5,7]

但没有:

[1,5,7][2,4,8][3,6,9] 

因为 1 和 7 已经一起出现(同样,3 和 9)。

我还想对 n=2 的子集执行此操作。 谢谢你!!

I need code that takes a list (up to n=31) and returns all possible subsets of n=3 without any two elements repeating in the same subset twice (think of people who are teaming up in groups of 3 with new people every time):

list=[1,2,3,4,5,6,7,8,9]

and returns

[1,2,3][4,5,6][7,8,9]

[1,4,7][2,3,8][3,6,9]

[1,6,8][2,4,9][3,5,7]

but not:

[1,5,7][2,4,8][3,6,9] 

because 1 and 7 have appeared together already (likewise, 3 and 9).

I would also like to do this for subsets of n=2.
Thank you!!

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

满天都是小星星 2024-12-23 13:09:21

这是我想出的:

from itertools import permutations, combinations, ifilter, chain

people = [1,2,3,4,5,6,7,8,9]

#get all combinations of 3 sets of 3 people
combos_combos = combinations(combinations(people,3), 3)

#filter out sets that don't contain all 9 people
valid_sets = ifilter(lambda combo: 
                     len(set(chain.from_iterable(combo))) == 9,
                     combos_combos)

#a set of people that have already been paired
already_together = set()
for sets in valid_sets:
    #get all (sorted) combinations of pairings in this set
    pairings = list(chain.from_iterable(combinations(combo, 2) for combo in sets))
    pairings = set(map(tuple, map(sorted, pairings)))

    #if all of the pairings have never been paired before, we have a new one
    if len(pairings.intersection(already_together)) == 0:
        print sets
        already_together.update(pairings)

这打印:

~$ time python test_combos.py 
((1, 2, 3), (4, 5, 6), (7, 8, 9))
((1, 4, 7), (2, 5, 8), (3, 6, 9))
((1, 5, 9), (2, 6, 7), (3, 4, 8))
((1, 6, 8), (2, 4, 9), (3, 5, 7))

real        0m0.182s
user        0m0.164s
sys         0m0.012s

Here's what I came up with:

from itertools import permutations, combinations, ifilter, chain

people = [1,2,3,4,5,6,7,8,9]

#get all combinations of 3 sets of 3 people
combos_combos = combinations(combinations(people,3), 3)

#filter out sets that don't contain all 9 people
valid_sets = ifilter(lambda combo: 
                     len(set(chain.from_iterable(combo))) == 9,
                     combos_combos)

#a set of people that have already been paired
already_together = set()
for sets in valid_sets:
    #get all (sorted) combinations of pairings in this set
    pairings = list(chain.from_iterable(combinations(combo, 2) for combo in sets))
    pairings = set(map(tuple, map(sorted, pairings)))

    #if all of the pairings have never been paired before, we have a new one
    if len(pairings.intersection(already_together)) == 0:
        print sets
        already_together.update(pairings)

This prints:

~$ time python test_combos.py 
((1, 2, 3), (4, 5, 6), (7, 8, 9))
((1, 4, 7), (2, 5, 8), (3, 6, 9))
((1, 5, 9), (2, 6, 7), (3, 4, 8))
((1, 6, 8), (2, 4, 9), (3, 5, 7))

real        0m0.182s
user        0m0.164s
sys         0m0.012s
一百个冬季 2024-12-23 13:09:21

试试这个:

from itertools import permutations

lst = list(range(1, 10))

n = 3
triplets = list(permutations(lst, n))
triplets = [set(x) for x in triplets]

def array_unique(seq):  
    checked = [] 
    for x in seq:
        if x not in checked: 
            checked.append(x) 
    return checked

triplets = array_unique(triplets)

result = []
m = n * 3
for x in triplets:
    for y in triplets:
        for z in triplets:
            if len(x.union(y.union(z))) == m:
                result += [[x, y, z]]

def groups(sets, i):
    result = [sets[i]]

    for x in sets:
        flag = True
        for y in result:
            for r in x:
                for p in y:
                    if len(r.intersection(p)) >= 2:
                        flag = False
                        break
                    else:
                        continue
                if flag == False:
                    break
        if flag == True:
            result.append(x)

    return result

for i in range(len(result)):
    print('%d:' % (i + 1))
    for x in groups(result, i):
        print(x)

n = 10 的输出:
http://pastebin.com/Vm54HRq3

Try this:

from itertools import permutations

lst = list(range(1, 10))

n = 3
triplets = list(permutations(lst, n))
triplets = [set(x) for x in triplets]

def array_unique(seq):  
    checked = [] 
    for x in seq:
        if x not in checked: 
            checked.append(x) 
    return checked

triplets = array_unique(triplets)

result = []
m = n * 3
for x in triplets:
    for y in triplets:
        for z in triplets:
            if len(x.union(y.union(z))) == m:
                result += [[x, y, z]]

def groups(sets, i):
    result = [sets[i]]

    for x in sets:
        flag = True
        for y in result:
            for r in x:
                for p in y:
                    if len(r.intersection(p)) >= 2:
                        flag = False
                        break
                    else:
                        continue
                if flag == False:
                    break
        if flag == True:
            result.append(x)

    return result

for i in range(len(result)):
    print('%d:' % (i + 1))
    for x in groups(result, i):
        print(x)

Output for n = 10:
http://pastebin.com/Vm54HRq3

送君千里 2024-12-23 13:09:21

这是我对您的问题的一个相当通用的解决方案的尝试。

from itertools import combinations

n = 3
l = range(1, 10)

def f(l, n, used, top):
    if len(l) == n:
        if all(set(x) not in used for x in combinations(l, 2)):
            yield [l]
    else:
        for group in combinations(l, n):
            if any(set(x) in used for x in combinations(group, 2)):
                continue
            for rest in f([i for i in l if i not in group], n, used, False):
                config = [list(group)] + rest
                if top:
                    # Running at top level, this is a valid
                    # configuration.  Update used list.
                    for c in config:
                        used.extend(set(x) for x in combinations(c, 2))
                yield config
                break

for i in f(l, n, [], True):
    print i

然而,对于n的高值来说它非常慢,对于n=31来说太慢了。我现在没有时间尝试提高速度,但我稍后可能会尝试。欢迎提出建议!

Here's my attempt of a fairly general solution to your problem.

from itertools import combinations

n = 3
l = range(1, 10)

def f(l, n, used, top):
    if len(l) == n:
        if all(set(x) not in used for x in combinations(l, 2)):
            yield [l]
    else:
        for group in combinations(l, n):
            if any(set(x) in used for x in combinations(group, 2)):
                continue
            for rest in f([i for i in l if i not in group], n, used, False):
                config = [list(group)] + rest
                if top:
                    # Running at top level, this is a valid
                    # configuration.  Update used list.
                    for c in config:
                        used.extend(set(x) for x in combinations(c, 2))
                yield config
                break

for i in f(l, n, [], True):
    print i

However, it is very slow for high values of n, too slow for n=31. I don't have time right now to try to improve the speed, but I might try later. Suggestions are welcome!

标点 2024-12-23 13:09:21

我的妻子在尝试为九人会议安排分组时遇到了这个问题;她不希望任何参加者重复参加。

我立即拿出了 itertools,然后被难住了,然后来到了 StackOverflow。但与此同时,我的非程序员妻子直观地解决了这个问题。关键的见解是创建一个井字游戏网格:

1 2 3 
4 5 6
7 8 9

然后简单地采取 3 组向下,3 组横向,3 组对角线环绕,3 组对角线相反,环绕。

那么你就可以在脑海中做到这一点。

- : 123,456,789 
| : 147,258,368 
\ : 159,267,348 
/ : 168,249,357 

我想下一个问题是这样的视觉方法你能走多远?它是否依赖于所需子集大小 * 子集数量 = 总元素数量的巧合?

My wife had this problem trying to arrange breakout groups for a meeting with nine people; she wanted no pairs of attendees to repeat.

I immediately busted out itertools and was stumped and came to StackOverflow. But in the meantime, my non-programmer wife solved it visually. The key insight is to create a tic-tac-toe grid:

1 2 3 
4 5 6
7 8 9

And then simply take 3 groups going down, 3 groups going across, and 3 groups going diagonally wrapping around, and 3 groups going diagonally the other way, wrapping around.

You can do it just in your head then.

- : 123,456,789 
| : 147,258,368 
\ : 159,267,348 
/ : 168,249,357 

I suppose the next question is how far can you take a visual method like this? Does it rely on the coincidence that the desired subset size * the number of subsets = the number of total elements?

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文