Python to iterate a number of possible combinations

[teflon]

Hi guys, I am a Python newbie so bear with me, I am trying to write a Python code that generates a query based on ten criteria represented as checkboxes, the user can select any 1-10 criteria in no particular order. so I am going to have 10 Combination 1 to 10 combination 10 possibilities and I realized using nested IF-ELSE is going to take forever. any ideas

[ichabod801]

I'm not sure exactly what you are talking about, but there is a combinations generator function in the itertools library. You might check that out.

[Escribblings]

I'm new to python too, and I'm not sure exactly that I understand what your trying to do.

Is it that there are 10 lists, and each list has 10 items, and each item is effectively a binary choice?

I think you'll want to be using the itertools module, either import it or just borrow the code you need.

This is an example of the total combinations of 1 list of 10 binary options.

# this code from itertools
# can also be invoked by changing 'combinations' to 'itertools.combinations' in your code
# or by starting with the line 'from itertools import combinations'

def combinations(iterable,r = None):
  # combinations('ABCD', 2) --> AB AC AD BC BD CD 
  # combinations(range(4), 3) --> 012 013 023 123 
  pool = tuple(iterable)
  n = len(pool)
  if r > n:
    return
  indices = list(range(r))
  yield tuple(pool[i] for i in indices)
  while True:
    for i in reversed(range(r)):
      if indices[i] != i + n - r:
        break
    else:
      return
    indices[i] += 1
    for j in range(i + 1,r):
      indices[j] = indices[j - 1] + 1
    yield tuple(pool[i] for i in indices)

# My example code

n= 0
a = (1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0)
for b in combinations(a,10):
	n += 1
	print (n,b)

Yields:

Output:
1 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
2 (1, 1, 1, 1, 1, 1, 1, 1, 1, 0)
3 (1, 1, 1, 1, 1, 1, 1, 1, 0, 1)
4 (1, 1, 1, 1, 1, 1, 1, 0, 1, 1)
5 (1, 1, 1, 1, 1, 1, 0, 1, 1, 1)
6 (1, 1, 1, 1, 1, 0, 1, 1, 1, 1)
7 (1, 1, 1, 1, 0, 1, 1, 1, 1, 1)
8 (1, 1, 1, 0, 1, 1, 1, 1, 1, 1)
9 (1, 1, 0, 1, 1, 1, 1, 1, 1, 1)
10 (1, 0, 1, 1, 1, 1, 1, 1, 1, 1)
11 (0, 1, 1, 1, 1, 1, 1, 1, 1, 1)
12 (1, 1, 1, 1, 1, 1, 1, 1, 0, 0)
13 (1, 1, 1, 1, 1, 1, 1, 0, 1, 0)
...
184756 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

[ichabod801]

Note that itertools.combinations is implemented in C. There is a Python equivalent given in the docs to help you understand what is going on. However, using the Python equivalent will be less efficient than the version available in itertools.

[scidam]

I don't clearly understand the question, but I wrote some text that could help you to find
solution for your case, I think.


Ok, we have a database presented by a list of tuples (key, value); That database could include multiple keys, e.g. data = [(key1, val1), (key1, val2), (key1, val3), (key2, val7)....]

data = [(x, 'message #{}'.format(x)) for x in range(2 ** 10)] #  [(key, value), ...] #kv-store, simple model 

You can choose another model of the db, or use external db solution. This is a simple model of a database.

Lets a user have selected some checkboxes, e.g. (0,0,0,0,0,0,1,0,1,0), this could be converted to some
binary value 0b0000001010 that coincedes to 10 (in decimal number system). So, we could treat that
any particular checkbox selection is already presented in binary form.

Now we need to make a query to our database. There are two general form of queries could be done here:
1) find records, where at least one checkbox is the same, as in the database;
2) find records, where all selected (unselected) checkboxes are the that, as in the database;


How to compare two keys (checkbox selection and record key)?

To check full equality, it is sufficient to use comparison operator ==.

0b0000001010 == 0b0000000101 => False
0b0000001010 == 0b0000001010 => True # all checkboxes should be the same, as in the db

If we need to perform comparison by "at least one checkbox equal" scheme, we can
use bitwise and operator.

bool(0b0000001010 & 0b0000000010)

Output:
True

bool(0b0000001010 & 0b1100000000)

Output:
False

Let we have:

user_selected_checkboxes = 0b0000000100

at_least_one_criteria_met = [v for k, v in data if k & user_selected_checkboxes]
len(at_least_one_criteria_met)

Output:
512

all_criteria_met = [v for k, v in data if k == user_selected_checkboxes]
all_criteria_met

Output:
['message #1']

You still need to adopt this for your needs. Note: searching in this cases has O(N) as
complexity estimation (you need to check all elements in the db). This might be inappropriate in case of millions records or more.

So, all combinations of 10 items could be masked as binary numbers from 0 to 1023. To traverse
all possible combinations (masks) in this case you just need iterate over range(0, 1024) and apply bin
function. Hope this helps.