Fruit bag swapping problem: fast python algorithm to swap packed items between two lists without changing item counts

Question

I have a coding problem that is very hard to explain, so I came up with this fruit bag swapping problem that is very easy to understand:

A smart fruiterer sells 3 kinds of fruits: apples (denoted as 'A'), bananas (denoted as 'B') and coconuts (denoted as 'C'). The weird thing about him is that he always prepares 10 bags (bag id 0 to 9), including 3 small bags that can contain 2 fruits, 3 medium bags that can contain 4 fruits, 3 large bags that can contain 8 fruits, and one extra large bag that can contain 16 fruits. He only puts in same type of fruit into each bag. This can be abstracted to the following python code:

import random
from string import ascii_uppercase

#length = 30
#max_size = 10
#bag_sizes = [random.randint(1, max_size) for _ in range(length)]

n_fruit = 3
bag_sizes = [2, 2, 2, 4, 4, 4, 8, 8, 8, 16]

random.seed(55)
fruiterer_bags = [[random.choice(ascii_uppercase[:n_fruit])] * bag_sizes[i] 
                  for i in range(len(bag_sizes))]
print(fruiterer_bags)

Output:

[['A', 'A'], ['A', 'A'], ['A', 'A'], 
 ['C', 'C', 'C', 'C'], ['B', 'B', 'B', 'B'], ['A', 'A', 'A', 'A'], 
 ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C'], 
 ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'], 
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B'], 
 ['A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A']]

Note that every day the fruiterer put fruits in each bag like this.

The supplier comes to the fruit shop every day with the same 10 bags, including 3 small, 3 medium, 3 large, 1 extra large. The bags are also assigned with id 0 to 9. He also only puts in same type of fruit in each bag, but the fruits he puts in each bag are not exactly the same as the fruiterer's. Every day he comes with the following bags:

random.seed(100)
supplier_bags = [[random.choice(ascii_uppercase[:n_fruit])] * bag_sizes[i] 
                 for i in range(len(bag_sizes))]
print(supplier_bags)

Output:

[['A', 'A'], ['B', 'B'], ['B', 'B'], 
 ['A', 'A', 'A', 'A'], ['C', 'C', 'C', 'C'], ['B', 'B', 'B', 'B'], 
 ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C'], 
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B'], 
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B'], 
 ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C']]

The smart thing about this fruiterer is that every time the supplier comes, he wants to swap some fruit bags because they are fresher. The supplier says "OK, fine. You can swap however you like, you can do as many swaps as you want, but:

1. I don't swap the bags with the same type of fruits in them;
2. I must have the same amount of each fruit after all the swaps;
3. I only swap whole bags, not individual fruit;
4. I only swap bags with same ids;
5. Each bag can only be swapped once;
6. PLEASE BE FAST!"

Since supplier_bags has to have the same amount of each fruit after the swaps, then fruiterer_bags will of course also have the same amount of each fruit after the swaps. In this way, both fruiterer and supplier do not change the amount of each fruit on paper, but the smart fruiterer always gets fresher fruits. Every day the fruiterer and supplier come with same bags of fruits, but hopefully they can find very different ways of swapping bags (radomness).

My question is: is there any algorithm to get one possible solution very fast. The expected output is the indices of the bags being swapped. For example, one solution could be

swap_ids = [1, 2, 3, 4]

and the supplier_bags after the swaps becomes:

new_supplier_bags = supplier_bags.copy()
for i in swap_ids:
    new_supplier_bags[i] = fruiterer_bags[i]
print(new_supplier_bags)

Output:

[['A', 'A'], ['A', 'A'], ['A', 'A'], 
 ['C', 'C', 'C', 'C'], ['B', 'B', 'B', 'B'], ['B', 'B', 'B', 'B'], 
 ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C'], 
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B'], 
 ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B'], 
 ['C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C']]

which still has the same amount of each fruit as before swaps. This can be checked by

assert sorted([f for bag in new_supplier_bags for f in bag]) == sorted(
              [f for bag in supplier_bags for f in bag])

Although I don't care about fruiterer_bagsat all, it must also have the same amount of each fruit after the swaps.

I don't want all possible solutions. I just want one fast solution with randomness, because in reality I am dealing with lists of more than 200 "bag"s with various sizes and many types of "fruit"s, which is infeasible for an enumeration. I want an algorithm to work for any given n_fruit, bag_sizes, fruiterer_bags and supplier_bags. I guess a greedy algorithm will do.

Also, Is there any way to quick check if there is a solution at all? If not, maybe we can say there is no solution after the greedy algorithm suggests e.g. 1000 wrong solutions (if fast enough).

Any suggestions?

Answer 1

Here is how:

import random
from string import ascii_uppercase

def swaps(bags1, bags2):
    fruits = sorted([i for j in bags1 for i in j])
    zipped = list(map(list, zip(bags1, bags2)))
    idxs = [i for i, (bags1, bags2) in enumerate(zipped) if bags1 != bags2]
    while True:
        random.shuffle(idxs)
        for n, i in enumerate(idxs):
            zipped[i].reverse()
            if fruits == sorted(fruit for bags1, _ in zipped for fruit in bags1):
                return idxs[:n + 1]
        zipped = list(map(list, zip(bags1, bags2)))

n_fruit = 3
bag_sizes = [2, 2, 2, 4, 4, 4, 8, 8, 8, 16]

random.seed(55)
fruiterer_bags = [[random.choice(ascii_uppercase[:n_fruit])] * i for i in bag_sizes]
random.seed(100)
supplier_bags = [[random.choice(ascii_uppercase[:n_fruit])] * i for i in bag_sizes]
random.seed()

print(swaps(fruiterer_bags, supplier_bags))

Running the code generates a random solution. Here are the results for 10 runs:

[1, 4, 2, 3]
[4, 5, 3]
[5, 4, 3]
[4, 3, 5]
[1, 2, 4, 3]
[3, 2, 4, 1]
[2, 3, 4, 1]
[3, 5, 4]
[4, 3, 5]
[5, 4, 3]

What I did in the code:

1. Define a list from zipping the two nested lists of strings, and define a list of all the indices of both nested lists that don't equal to each others at the same index.

2. Shuffle the list of indices and loop through the indice, reversing the element of the zipped list at the index of each iteration.

3. At any point in the looping, if all the strings sorted in the first element of each element in the zipped list equals to all the strings sorted in the original first nested list, we got a solution, can we can return it.