Python limited combination

Question

I have a list with 200 elements. I want to randomly calculate 10% of all the combinations of length k of those elements and store the result in a list.

For example:

Assume 'ABCD' as in ['A', 'B', 'C', 'D'] and I want combinations of length 2. All possible combinations in this case would be 6 (n! / ((n-k)! x k!)). I want to get 10% of that which is 0.6 -> 1 (round up).

I tried itertools.combinations('ABCD', 2) but it gives me all combinations.

---

Here's some more information about my problem.

I have

all_points_coordinates =  [
    [-1.6339171050450814, 2.5160117038362722], 
    [-1.7207293090531386, 2.4574561328669748], 
    [0.10469849010750323, 2.9981724810572872],
]

and I want to calculate combinations of 3 of them and use

def all_way(points):
    point = len(points)
    allrout = []
    allrout = list(itertools.permutations(points, point))
    return allrout

but it gives me all combinations of my points. When I run it for 100 points it is very time consuming so I want to calculate just a limited number of these combinations.

Answer 1

We can generate the random combinations using random.sample, and use a set to ensure we don't generate any combination more than once. Here's a simple demo.

from random import seed, sample

seed(42)

def random_combinations(seq, size, num):
    combos = set()
    while len(combos) < num:
        item = sample(seq, size)
        combos.add(tuple(item))
    return list(combos)

# test

data = [
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19),
]

# Make 20 random 3-element combinations
combos = random_combinations(data, 3, 20)
for i, item in enumerate(combos, 1):
    print('{:>2}: {}'.format(i, item))

output

 1: ((2, 3), (12, 13), (8, 9))
 2: ((6, 7), (18, 19), (4, 5))
 3: ((2, 3), (16, 17), (18, 19))
 4: ((0, 1), (4, 5), (12, 13))
 5: ((14, 15), (10, 11), (4, 5))
 6: ((2, 3), (0, 1), (8, 9))
 7: ((6, 7), (16, 17), (0, 1))
 8: ((12, 13), (2, 3), (8, 9))
 9: ((6, 7), (14, 15), (8, 9))
10: ((10, 11), (18, 19), (8, 9))
11: ((0, 1), (14, 15), (2, 3))
12: ((18, 19), (10, 11), (6, 7))
13: ((18, 19), (12, 13), (0, 1))
14: ((10, 11), (8, 9), (4, 5))
15: ((8, 9), (2, 3), (6, 7))
16: ((2, 3), (0, 1), (6, 7))
17: ((16, 17), (6, 7), (12, 13))
18: ((2, 3), (12, 13), (18, 19))
19: ((0, 1), (2, 3), (6, 7))
20: ((6, 7), (10, 11), (2, 3))

As tobias_k mentions in the comments, this code is only suitable when num is not too close to the total number of combinations. If you want < 50% of the total number of combinations it should be fine, but beyond that it will have a high chance of re-generating combinations that it's already generated, which will cause it to loop for a long time.

---

Note that this code considers ((2, 3), (12, 13), (8, 9)) to be distinct from a tuple containing those 3 pairs in a different order, eg ((2, 3), (8, 9), (12, 13)).

If you don't want that we can make our items into sets. We need to use frozenset for this, since normal sets are mutable and therefore unhashable and hence cannot be set items.

from random import seed, sample

seed(42)

def random_combinations(seq, size, num):
    combos = set()
    while len(combos) < num:
        item = sample(seq, size)
        combos.add(frozenset(item))
    return [tuple(u) for u in combos]

# test

data = [
    (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), 
    (10, 11), (12, 13), (14, 15), (16, 17), (18, 19),
]

# Make 20 random 3-element combinations
combos = random_combinations(data, 3, 20)
for i, item in enumerate(combos, 1):
    print('{:>2}: {}'.format(i, item))

output

 1: ((0, 1), (2, 3), (6, 7))
 2: ((0, 1), (2, 3), (8, 9))
 3: ((16, 17), (6, 7), (0, 1))
 4: ((12, 13), (2, 3), (18, 19))
 5: ((12, 13), (2, 3), (8, 9))
 6: ((12, 13), (18, 19), (0, 1))
 7: ((8, 9), (4, 5), (10, 11))
 8: ((16, 17), (2, 3), (18, 19))
 9: ((8, 9), (6, 7), (14, 15))
10: ((0, 1), (4, 5), (12, 13))
11: ((8, 9), (10, 11), (18, 19))
12: ((10, 11), (6, 7), (2, 3))
13: ((0, 1), (14, 15), (2, 3))
14: ((10, 11), (18, 19), (6, 7))
15: ((8, 9), (2, 3), (6, 7))
16: ((4, 5), (6, 7), (18, 19))
17: ((8, 9), (4, 5), (2, 3))
18: ((16, 17), (4, 5), (6, 7))
19: ((16, 17), (6, 7), (12, 13))
20: ((4, 5), (10, 11), (14, 15))

Answer 2

Another rather simple possibility: Generate all the combinations, but only keep those where some random variable is < 0.1 to get (roughly) 10% of the resulting combinations.

>>> sum(1 for _ in itertools.combinations(range(100), 3)) # total count for comparison
161700
>>> res = [c for c in itertools.combinations(range(100), 3) if random.random() < 0.1]
>>> len(res)
16227

Compared with using random.sample, this has the advantage that it does not need to keep all the combinations in memory, although it will still generate all the combinations, but discard 90% of them immediately. Also, the result will be only roughly 10% of the combinations, but not exactly. For large numbers, that should not be too much of a problem, though.

Answer 3

If you don't want to calculate all combinations in advance before picking a small subset of them, you have two options:

1. Ugly, but does the job

   • Shuffle the elements of your list. Add the result to a set
   • Continue until the set has the desired length.

2. Beautiful but complicated

   • Create a list of indices < n! (where n is the number of elements in your list)
   • Calculate the combination for each index (similar to this question.

Answer 4

Option 1 (not random but generates what is needed only):

Take the first 10% percent of the results returned by itertools.combinations().

import itertools
from math import factorial, ceil    

original = 'ABCD'
k = 2
percentage = 0.1
configurations = factorial(len(original)) / (factorial(len(original) - k) * factorial(k))
take = ceil(percentage * configurations)
res = []
for i, comb in enumerate(itertools.combinations(original, k), 1):
    res.append(comb)
    if i == take:
        break
print(res, len(res))

---

Option 2 (random but generates the full list first):

Take 10% percent of the results returned by itertools.combinations() randomly. Requires Python 3.6 because of random.choices()

# Python 3.6 you can do this
import random
import itertools
from math import factorial, ceil

original = 'ABCD'
k = 2
percentage = 0.1
configurations = factorial(len(original)) / (factorial(len(original) - k) * factorial(k))
take = ceil(percentage * configurations)
res = random.choices([x for x in itertools.combinations(original, k)], k=take)

original can also be a list.

Answer 5

ı solve my problem like this

point=  len(points)
p=int(point*10/100)
allrout = list(itertools.islice(itertools.permutations(points, point),p ))
print(len(allrout))
return allrout