How can I combine elements of list in pairs in every iteration without repetition?

Question

I am working on a genetic algorithm in python. In my problem I store individuals in a list like that:

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

In every iteration there is some fixed probability that each individual will die, and therefore it will be deleted from the list.

What is more, in every iteration individuals pair up randomly, for example:

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

and there is some probability that these pairs will have a child, which will be added to the list as the next number (11, 12 etc.)

Each pair may appear only once, so I have to store each pair and after choosing randomly two individuals, check if they haven't been a pair already.

I managed to do all of that:

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)

but in some cases, after a few iterations I have at least 2 elements left, that have already been paired up and I end up with an infinite loop:

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

and so on.

Is there any efficient way to check in every iteration if it is possible to create any new pairs, and if not, break the while loop? Of course, I can make combinations of elements left in pop_temp list after every reproduction process and check if any of those combinations aren't in used_pairs set, but with many iterations and high reproduction probability it's going to be extremely inefficient, because there will be thousands of elements in my list.

Answer 1

Seeing as the generator of pairs is stateful between calls, I would wrap the functionality inside a class. The instance will store used pairs to ensure we don't repeat anything. Using itertools.combinations we can find all of the possible pairs. We can randomly sample the combinations, and then keep track of all the individuals we used for that round.

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

Example usage

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

For your main code, we can do something similar for how we create new creatures.

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

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

Now the logic of your program becomes much easier to read!

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 []

Answer 2

I suggest using iterertools.combinations() to generate your pairs. This will guarantee that no element will repeat in a pair. If you need to randomly select from those pairs, you can use random.sample().

Answer 3

I would suggest using a dictionary to keep track of pairings. This will allow you to systematically go through the population and pair individuals with remaining candidates that have not been paired with that one. This way, if there are no more eligible partners, the individual is simply not paired and the pairing loop can eventually exit.

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)

Sample Run:

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]