如何在每次迭代中将列表元素成对组合，且不重复？

Question

我正在使用Python编写遗传算法。在我的问题中，我将个体存储在一个列表中，如下所示：

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

每次迭代中，每个个体都有一定的固定概率死亡，因此它将从列表中删除。

此外，在每次迭代中，个体会随机配对，例如：

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

有一定的概率这些配对会有孩子，然后将孩子添加到列表中作为下一个数字（11，12等）。

每对只能出现一次，所以我必须存储每对，并在随机选择两个人之后检查他们是否已经成为一对。

我成功地完成了所有这些操作：

reproducing_prob = 0.1 #probability of reproduction
death_prob = 0.1 #probability of death
pop_size = 10 #starting population size
pop_start = list(range(1, pop_size+1))
used_pairs = set() #storing pairs that already appeared
new_creature = 10

for day in range(10):
    
    print("\nDay ", day)
    print("Population: ", pop_start)
    dead_creatures = []
    
    for creature in pop_start: #iterating through whole list to check if creatures die
        death = np.random.uniform(0,1)
        if death < death_prob:
            print("Dead: ", creature)
            dead_creatures.append(creature)  
            
    pop_start = [creature for creature in pop_start if creature not in dead_creatures]

    pop_temp = pop_start.copy()
    while len(pop_temp) > 1: #looping through list until there aren't enough elements to pair them up
        idx1, idx2 = random.sample(range(0, len(pop_temp)), 2) 
        rand1, rand2 = pop_temp[idx1], pop_temp[idx2] 
        print("Found pair: ", rand1, rand2)
        
        if ((rand1, rand2) not in used_pairs) and ((rand2, rand1) not in used_pairs): #check if random pair hasn't been already used
            for i in sorted([idx1, idx2], reverse=True):
                pop_temp.pop(i)
            pair = rand1, rand2
            used_pairs.add(pair)
            reproducing = np.random.uniform(0,1)
            if reproducing < reproducing_prob:
                pop_size += 1
                new_creature += 1
                print("New creature! ", new_creature)
                pop_start.append(new_creature)

但在某些情况下，经过几次迭代后，我至少还剩下2个已经配对的元素，最终导致无限循环：

Day  0
Population:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Found pair:  10 3
Found pair:  7 5
New creature!  11
Found pair:  8 2
Found pair:  9 1
Found pair:  6 4

Day  1
Population:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Dead:  8
Found pair:  6 10
Found pair:  1 11
Found pair:  4 5
Found pair:  2 9
Found pair:  3 7

Day  2
Population:  [1, 2, 3, 4, 5, 6, 7, 9, 10, 11]
Dead:  6
Found pair:  5 11
Found pair:  10 1
Found pair:  3 2
Found pair:  9 7

Day  3
Population:  [1, 2, 3, 4, 5, 7, 9, 10, 11]
Found pair:  11 9
Found pair:  4 7
Found pair:  5 10
Found pair:  2 1

Day  4
Population:  [1, 2, 3, 4, 5, 7, 9, 10, 11]
Dead:  10
Found pair:  5 3
New creature!  12
Found pair:  2 7
Found pair:  9 1
Found pair:  4 9
Found pair:  1 11
Found pair:  11 1
Found pair:  1 11
Found pair:  11 1

等等其他的事情。

有没有一种有效的方式，在每次迭代中检查是否可以创建任何新的对，如果不行，则退出while循环？当然，我可以在每次繁殖过程后将剩余的元素组合在pop_temp列表中，并检查这些组合中是否有任何一个不在used_pairs集合中，但是随着许多迭代和高繁殖概率，这将变得极其低效，因为我的列表中将有成千上万个元素。

- MKorona

---

个人可以出现在多个配对中吗？比如(1,2),(2,3)？ - flakes

不行，每次迭代中，每个个体只能出现在一个配对中。 - MKorona

你能否提供一个例子，展示一下你的解决方案无法正常工作的情况？ - deadshot

当然，在问题中我添加了一个示例。 - MKorona

Answer 1

考虑到生成器在不同的调用之间具有状态，我会将其功能包装在一个类中。该实例将存储已使用的成对元素以确保我们不重复使用任何东西。使用itertools.combinations，我们可以找到所有可能的成对元素组合。我们可以随机抽样这些组合，并记录当前轮次中所使用的所有元素。

class PairGenerator:
    def __init__(self):
        self.used_pairs = set()

    def next_pairs(self, individuals):
        """
        Return unique pairs of individuals that haven't been seen before.
        In each call, we will look at the history of used_pairs to avoid duplicates.
        In each call, each individual may only be used in one pair.
        """

        # Find all pairs that could be used. Also ensure data contains no duplicates
        possible_pairs = list(itertools.combinations(set(individuals), r=2))
        # Keep track of which individuals were used this call.
        used_individuals = set()

        # Add randomness when sampling possible pairs
        for a, b in random.sample(possible_pairs, len(possible_pairs)):
            # Sort the pair to ensure [a, b] collides with [b, a]
            if a > b:
                a, b = b, a
            # Check both the individuals haven't been used in this cycle
            if a in used_individuals or b in used_individuals:
                continue
            # Check that the pair has not been seen before.
            if (a, b) in self.used_pairs:
                continue

            # Register pair and individuals before yielding
            self.used_pairs.add((a, b))
            used_individuals.add(a)
            used_individuals.add(b)
            yield a, b

示例用法

generator = PairGenerator()
individuals = [1, 2, 3, 4, 5, 6,  7,  8,  9, 10]
for i in range(4):
    pairs = list(generator.next_pairs(individuals))

    print(f"Iteration {i}:")
    print(f"  {individuals=}")
    print(f"  {pairs=}")
    print(f"  used_pairs={len(generator.used_pairs)}")

    individuals.append(individuals.pop(0) + 10)

Iteration 0:
  individuals=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  pairs=[(1, 10), (2, 4), (3, 9), (5, 6), (7, 8)]
  used_pairs=5
Iteration 1:
  individuals=[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  pairs=[(3, 7), (2, 8), (5, 9), (6, 10), (4, 11)]
  used_pairs=10
Iteration 2:
  individuals=[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  pairs=[(3, 11), (6, 12), (7, 9), (4, 8), (5, 10)]
  used_pairs=15
Iteration 3:
  individuals=[4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
  pairs=[(7, 11), (4, 13), (8, 10), (6, 9), (5, 12)]
  used_pairs=20

对于您的主代码，我们可以采用类似的方式创建新的生物。

class CreatureGenerator:
    def __init__(self):
        self.last_creature = 0

    def next_creature(self):
        self.last_creature += 1
        return self.last_creature

现在，您的程序逻辑变得更容易阅读了！

pair_gen = PairGenerator()
creature_gen = CreatureGenerator()

reproducing_prob = 0.1  # probability of reproduction
death_prob = 0.1  # probability of death
pop_size = 10  # starting population size

creatures = set(creature_gen.next_creature() for _ in range(pop_size))

day = 0
while creatures:
    day += 1

    print("\nDay:", day)
    print("Population:", len(creatures), list(creatures))

    dead_creatures = {
        creature for creature in creatures
        if random.uniform(0, 1) < death_prob
    }
    creatures -= dead_creatures

    creature_pairs = list(pair_gen.next_pairs(creatures))
    new_creatures = {
        creature_gen.next_creature() for _ in creature_pairs
        if random.uniform(0, 1) < reproducing_prob
    }
    creatures.update(new_creatures)

    print("Dead Creatures:", len(dead_creatures), list(dead_creatures))
    print("Creature pairs:", len(creature_pairs), list(creature_pairs))
    print("New creatures:", len(new_creatures), list(new_creatures))

Day: 1
Population: 10 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Dead Creatures: 1 [1]
Creature pairs: 4 [(2, 4), (3, 6), (5, 9), (7, 8)]
New creatures: 2 [11, 12]

Day: 2
Population: 11 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Dead Creatures: 1 [2]
Creature pairs: 5 [(4, 10), (5, 6), (3, 8), (11, 12), (7, 9)]
New creatures: 1 [13]

Day: 3
Population: 11 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
Dead Creatures: 1 [13]
Creature pairs: 5 [(4, 7), (6, 11), (5, 10), (8, 9), (3, 12)]
New creatures: 1 [14]

Day: 4
Population: 11 [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14]
Dead Creatures: 2 [9, 12]
Creature pairs: 4 [(4, 14), (10, 11), (6, 8), (5, 7)]
New creatures: 0 []

Day: 5
Population: 9 [3, 4, 5, 6, 7, 8, 10, 11, 14]
Dead Creatures: 1 [11]
Creature pairs: 4 [(4, 6), (3, 7), (10, 14), (5, 8)]
New creatures: 0 []

Day: 6
Population: 8 [3, 4, 5, 6, 7, 8, 10, 14]
Dead Creatures: 0 []
Creature pairs: 3 [(8, 10), (6, 7), (3, 5)]
New creatures: 0 []

Day: 7
Population: 8 [3, 4, 5, 6, 7, 8, 10, 14]
Dead Creatures: 1 [4]
Creature pairs: 2 [(5, 14), (3, 10)]
New creatures: 0 []

Day: 8
Population: 7 [3, 5, 6, 7, 8, 10, 14]
Dead Creatures: 1 [7]
Creature pairs: 1 [(6, 14)]
New creatures: 0 []

Day: 9
Population: 6 [3, 5, 6, 8, 10, 14]
Dead Creatures: 1 [6]
Creature pairs: 1 [(3, 14)]
New creatures: 0 []

Day: 10
Population: 5 [3, 5, 8, 10, 14]
Dead Creatures: 0 []
Creature pairs: 1 [(8, 14)]
New creatures: 1 [15]

Day: 11
Population: 6 [3, 5, 8, 10, 14, 15]
Dead Creatures: 0 []
Creature pairs: 1 [(8, 15)]
New creatures: 0 []

Day: 12
Population: 6 [3, 5, 8, 10, 14, 15]
Dead Creatures: 3 [10, 14, 15]
Creature pairs: 0 []
New creatures: 0 []

Day: 13
Population: 3 [3, 5, 8]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 14
Population: 3 [3, 5, 8]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 15
Population: 3 [3, 5, 8]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 16
Population: 3 [3, 5, 8]
Dead Creatures: 1 [8]
Creature pairs: 0 []
New creatures: 0 []

Day: 17
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 18
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 19
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 20
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 21
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 22
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 23
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 24
Population: 2 [3, 5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 25
Population: 2 [3, 5]
Dead Creatures: 1 [3]
Creature pairs: 0 []
New creatures: 0 []

Day: 26
Population: 1 [5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 27
Population: 1 [5]
Dead Creatures: 0 []
Creature pairs: 0 []
New creatures: 0 []

Day: 28
Population: 1 [5]
Dead Creatures: 1 [5]
Creature pairs: 0 []
New creatures: 0 []

- flakes

---

没错，但是在繁殖过程中，也就是向列表中添加新元素后，我必须从头开始进行抽样，并且在每次迭代中都要重复此过程，那么如果按照你的方式进行操作，有可能会出现一些重复的对，这种情况是否可以避免呢？ - MKorona

@MKorona，这个答案的更新对您有帮助吗？如果没有，我很乐意解释更多我的过程！ - flakes

Answer 2

我建议使用itertools.combinations()来生成你的对。这将保证在每个对中没有元素重复。如果你需要从这些对中随机选择，可以使用random.sample()。

- Code-Apprentice

Answer 3

我建议使用字典来跟踪配对。这将使您系统地浏览人口，并将未与该个体配对的剩余候选者进行配对。这样，如果没有更多合适的伴侣，那么该个体就不会被配对，配对循环最终可以退出。

import random
from collections import defaultdict

reproducing_prob = 0.1 #probability of reproduction
death_prob       = 0.1 #probability of death
pop_size         = 10 #starting population size
population       = list(range(1, pop_size+1))
next_id          = pop_size+1
paired           = defaultdict(set)   # {creature:set of paired creatures}

for day in range(10):
    print("Day",day)
    print("  population",population)
    deaths = {c for c in population if random.random()<death_prob}
    print("  deaths:",deaths or None)
    population = [c for c in population if c not in deaths] # remove deads
    singles    = random.sample(population,len(population))  # randomizes pairs
    while singles:          # systematically consume list
        a = singles.pop(0)  # remove first individual
        b = next((c for c in singles if c not in paired[a]),0)
        if not b: continue  # no eligible candidate (i.e. no pairing)
        print("  pair",(a,b))
        singles.remove(b)   # remove paired individual
        paired[a].add(b)    # track pairs
        paired[b].add(a)    # in both order
        if random.random()<reproducing_prob: # reproduce ?
            print("  NewCreature!",next_id)
            population.append(next_id)       # add individual
            next_id += 1                     # unique numbering 
print("Final Population:",population)

样例运行：

Day 0
  population [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  deaths: {4}
  pair (8, 1)
  NewCreature! 11
  pair (6, 7)
  pair (2, 10)
  pair (3, 5)
Day 1
  population [1, 2, 3, 5, 6, 7, 8, 9, 10, 11]
  deaths: None
  pair (7, 11)
  pair (1, 10)
  NewCreature! 12
  pair (9, 2)
  pair (8, 5)
  NewCreature! 13
  pair (6, 3)
Day 2
  population [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13]
  deaths: {9, 3, 5}
  pair (12, 7)
  pair (13, 1)
  pair (10, 8)
  pair (11, 2)
Day 3
  population [1, 2, 6, 7, 8, 10, 11, 12, 13]
  deaths: {11, 13}
  pair (10, 7)
  pair (8, 2)
  pair (1, 12)
Day 4
  population [1, 2, 6, 7, 8, 10, 12]
  deaths: {8, 1, 12}
  pair (10, 6)
  pair (2, 7)
Day 5
  population [2, 6, 7, 10]
  deaths: None
  pair (6, 2)
Day 6
  population [2, 6, 7, 10]
  deaths: None
Day 7
  population [2, 6, 7, 10]
  deaths: None
Day 8
  population [2, 6, 7, 10]
  deaths: None
Day 9
  population [2, 6, 7, 10]
  deaths: None
Final Population: [2, 6, 7, 10]

- Alain T.

---

这比较复杂。OP需要对多个回合进行此操作，每次都有不同的列表数据，同时还要确保在连续的回合中不重复使用任何一对。 - flakes

@flakes，我曾经误解了那一部分（对我来说，有任何持久的生物状态阻止下一代重新配对是违反直觉的）。我调整了答案以满足这个条件。 - Alain T.