0

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
5
  • It's adding 1 to a base 3 number.
    – interjay
    Jul 6, 2022 at 10:51
  • Thank you for your reply, what if the total size for each collection are different? That is, column 0 could have 1-3 items, column 2 could have 1-4 items and column 3 could have 1-5 items. Jul 6, 2022 at 10:53
  • Should not be much different, except you have to do it by hand, and the values of the "digits" would not be 3^0, 3^1, 3^2 etc. but e.g. 1, 4, 4*3, 4*3*5, etc.
    – tobias_k
    Jul 6, 2022 at 10:58
  • To be clear: You are looking for a way to: Given a number n, find the n-th element in the product (not a permutation!) of the different lists, without generating all the elements before that?
    – tobias_k
    Jul 6, 2022 at 10:59
  • Yes, thank you for this clarifying fact that I am looking for! That's what I'm looking for, and to do it it numerically without repeats. (I'm deliberately trying to avoid a nested for loop) Jul 6, 2022 at 11:01

2 Answers 2

1

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
4
  • Thank you so much for this. I changed the Replit code to use your solution. I plan to use the algorithm in this Enumerating Cartesian product while minimizing repetition Why do I want to do this? I wrote a userspace M:N thread scheduler and it round robin load balances work of lightweight threads over kernel threads. This is a bit like Golang's scheduler. Jul 6, 2022 at 11:34
  • Your work lets me load balance lightweight threads, with that other stackoverflow post, I can even EVENLY load balance arbitrarily nested loops! So every loop iteration is running in parallel. I need to work out how to shift priority between different parts of loops and you could create the illusion that some things are going on faster than others. See notes on cancellation trees and register loop primitive. Jul 6, 2022 at 11:38
  • Your bonus of getting the position in the nth product allows installation and business processes to be arbitrarily resumed. I propose Error messages in software, backend business event processing should print out a code that corresponds to the nth product position, that way you can resume from where you leftoff! you could even save it for database crash recovery. Jul 6, 2022 at 11:40
  • To clarify, an evenly distributed cartesian product doesn't look like 001, 002, 003, 010, 011, it looks like this 111, 222. I'll post an answer what I ended up using for reference. Jul 6, 2022 at 12:19
0

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÷

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.