Imagine this loop:
for i in range(3):
for j in range(3):
for k in range(3):
print("{}{}{}".format(letter, number, symbol))
I want to generate this sequence numerically - without a nested for loop, by manipulating the i, j and k values. What's the formula to covering every permutation of these 3 values?
Given 3 numbers I, j, k how do I calculate the next position without repeats? I should add that i, j, k might have different sizes.
I've tried using python itertools permutations and I've used a counting algorithm.
I tried to generate it with a counting algorithm. But I think there's something obvious in my counting algorithm that I'm missing, but I'm not sure what it is.
Imagine a function called .tick that produces the next item in the sequence without repeats.
My counting algorithm looks like this. You can find it on Repl.it here.
class Tick:
def __init__(self, collections, func):
self.collections = collections
self.indexes = []
self.loops = 0
self.reset = -1
self.func = func
self.started = False
for collection in collections:
self.indexes.append(0)
def size(self):
total = len(self.collections[0])
for collection in self.collections[1:]:
total = total * len(collection)
return total
def tick(self):
if self.started:
if self.reset != -1:
self.indexes[self.reset 1] = 0
for index in range(self.reset 1, len(self.indexes)):
self.indexes[index] = 0
self.reset = -1
else:
self.loop = len(self.indexes) - 1
while self.loop != -1 and self.indexes[self.loop] == len(self.collections[self.loop]) - 1:
self.loop = self.loop - 1
if self.loop == -1:
return
self.indexes[self.loop] = self.indexes[self.loop] 1
if self.loop < len(self.indexes) - 1:
self.reset = self.loop
else:
self.started = True
items = []
for loop in range(len(self.indexes)):
items.append(self.collections[loop][self.indexes[loop]])
return self.func(items)
a = ["0", "1", "2"]
b = ["0", "1", "2"]
c = ["0", "1", "2"]
def printer(items):
output = ""
for item in items:
output = item
return output
ticker = Tick([a, b, c], printer)
print(ticker.size())
for index in range(ticker.size()):
print(ticker.tick())
Unfortunately it produces the following
27
000
001
002
012
010
011
012
022
020
021
022
122
100
101
102
112
110
111
112
122
120
121
122
222
200
201
202
Notice the following are duplicated. I used this duplicate line finder.
COUNT | LINE
-----------------------------------------------------
3 | 122
2 | 012
2 | 022
2 | 112
1 | 000
1 | 001
1 | 002
1 | 010
1 | 011
1 | 020
1 | 021
1 | 100
1 | 101
1 | 102
1 | 110
1 | 111
1 | 120
1 | 121
1 | 200
1 | 201
1 | 202
1 | 222
-----------------------------------------------------
27 | TOTAL LINES
22 | DISTINCT LINES
CodePudding user response：
If I understand your question correctly, you are looking for a way to: Given a number n, find the n-th element in the product of the different lists, without generating all the elements before that. You can do that similar to converting a number to a different base, except there might be a different base for each digit, and instead of returning the digits themselves, you are getting those elements from the corresponding lists.
def nth_product(list_of_lists, n):
res = []
# reversed to match order of itertools.product
for lst in reversed(list_of_lists):
n, r = divmod(n, len(lst))
res.append(lst[r])
return tuple(reversed(res))
Similarly, you can compute the position of a given product in the list of products, to e.g. get the product directly after some other product:
def position(list_of_lists, tup):
t = 1
res = 0
for lst, x in zip(reversed(list_of_lists), reversed(tup)):
res = t * lst.index(x)
t *= len(lst)
return res
Comparing that with what itertools.product produces:
import itertools
list_of_lists = [[1,2], [3,4,5,6], [7,8,9]]
for n, prod in enumerate(itertools.product(*list_of_lists)):
print(n, prod, nth_product(list_of_lists, n), prod_position(list_of_lists, prod))
Result:
0 (1, 3, 7) (1, 3, 7) 0
1 (1, 3, 8) (1, 3, 8) 1
...
23 (2, 6, 9) (2, 6, 9) 23
CodePudding user response：
This is the code I ended up using. I had an additional requirement that I wanted the cartesian product to be evenly spread out too! This uses tobias_k answer to produce the nth product of the nested loop. I also wanted to evenly spread the evaluation of nested loops: so rather than 001 002 003 010 011 100 100 101 111 I wanted 111 222 333. Please see this stackoverflow answer, Enumerating Cartesian product while minimizing repetition for the formula for evenly spreading out the cartesian product. Secret, use more modulo!
class Tick:
def __init__(self, collections, func):
self.collections = collections
self.n = 0
self.func = func
self.current = []
for item in range(len(self.collections)):
self.current.append(0)
def size(self):
total = len(self.collections[0])
for collection in self.collections[1:]:
total = total * len(collection)
return total
def tick(self):
items = []
n = self.n
self.indexes = []
# reversed to match order of itertools.product
for collection in reversed(self.collections):
n, r = divmod(n, len(collection))
self.indexes.append(r)
for loop in range(len(self.collections)):
previous = 0
for mod in range(0, len(self.collections)):
previous = previous self.indexes[mod]
self.indexes[loop] = previous % len(self.collections[loop])
for loop, item in enumerate(self.indexes):
items.append(self.collections[loop][item])
self.n = self.n 1
return self.func(items)
a = ["a", "b", "c"]
b = ["1", "2", "3"]
c = ["÷", "×", "("]
def printer(items):
output = ""
for item in items:
output = item
return output
ticker = Tick([a, b, c], printer)
print(ticker.size())
for index in range(ticker.size()):
print(ticker.tick())
print("CORRECT")
for letter in a:
for number in b:
for symbol in c:
print("{}{}{}".format(letter, number, symbol))
For the curious, this is what it produces:
a1÷
b2(
c3×
b3÷
c1(
a2×
c2÷
a3(
b1×
b3×
c1÷
a2(
c2×
a3÷
b1(
a1×
b2÷
c3(
c2(
a3×
b1÷
a1(
b2×
c3÷
b3(
c1×
a2÷
Notice after the obvious sequence
a1÷ 1 1 1
b2( 2 2 2
c3× 3 3 3
We get
b3÷ which is 2 3 1
c1( which is 3 1 3
a2× which is 1 2 2
And so on, evenly spread out!