How to create a eventually fair but biased distribution of Cartesian product of sets

Question

Say I have X or 3 sets of different sizes.

So 3×4×5

I want to generate a probability distribution of the Cartesian of these sets that eventually and is guaranteed to cover every item.

Which based on my other answer I can generate the Nth Cartesian product by

items = []
N = self.N
for item in sets:
 N, r = divmod(N, len(item))
 items.append(item[r])
self.N = self.N + 1

Now I want to bias the distribution of the set to be unfair.

For example, If I have three sets a, b and c. I want to pick an item from a more often than b and an item of b more often than c but I want all items to eventually occur.

One inefficient idea I have is to generate all the indexed of every Nth position and order them based on a distribution but I am not sure how to do that.

Why am I trying to do this? I am trying to schedule things.

Answer 1

I think I found a solution. It's also incremental and small change. We introduce a frequency array. This is the priority order. 0 means that this column shall grow the least, then 1 means this column shall grow the most. 2 means that this column shall grow more than 0 but less than 1. I'm not sure why.

letters = ["A", "B", "C", "D"]
numbers = ["1", "2", "3", "4"]
symbols = ["÷", "×", "(", "&"]
freq = [2, 0, 1]

class Concurrent:
  def __init__(self, sets):
    self.sets = sets
    self.N = 0
  
  def size(self):
    total = len(self.sets[0])
    for item in self.sets[1:]:
      total = total * len(item)
    return total

  def reset(self):
    self.N = 0

  def fairtick(self):
    combo = []
    N = self.N
    for index, item in enumerate(self.sets):
      N, r = divmod(N, len(item))
      combo.append(r)
    self.N = self.N + 1
    results = ""
    for index, item in enumerate(combo):
      results += self.sets[index][item]
    return results

  def biasedtick(self):
    combo = [0] * len(self.sets)
    N = self.N
    for index, item in enumerate(self.sets):
      N, r = divmod(N, len(item))
      combo[freq[index]] = r
    self.N = self.N + 1
    results = ""
    for index, item in enumerate(combo):
      results += self.sets[index][item]
    return results

print("FAIR")
cl = Concurrent([letters, numbers, symbols])
s1 = set()
for index in range(cl.size()):
  value = cl.fairtick()
  print(value)
  s1.add(value)
print("")
print("BIASED")
print("")

cl2 = Concurrent([letters, numbers, symbols])
s2 = set()
for index in range(cl2.size()):
  value = cl2.biasedtick()
  print(value)
  s2.add(value)
assert s1 == s2

Here's the output:

FAIR
A1÷
B1÷
C1÷
D1÷
A2÷
B2÷
C2÷
D2÷
A3÷
B3÷
C3÷
D3÷
A4÷
B4÷
C4÷
D4÷
A1×
B1×
C1×
D1×
A2×
B2×
C2×
D2×
A3×
B3×
C3×
D3×
A4×
B4×
C4×
D4×
A1(
B1(
C1(
D1(
A2(
B2(
C2(
D2(
A3(
B3(
C3(
D3(
A4(
B4(
C4(
D4(
A1&
B1&
C1&
D1&
A2&
B2&
C2&
D2&
A3&
B3&
C3&
D3&
A4&
B4&
C4&
D4&

BIASED

A1÷
A1×
A1(
A1&
B1÷
B1×
B1(
B1&
C1÷
C1×
C1(
C1&
D1÷
D1×
D1(
D1&
A2÷
A2×
A2(
A2&
B2÷
B2×
B2(
B2&
C2÷
C2×
C2(
C2&
D2÷
D2×
D2(
D2&
A3÷
A3×
A3(
A3&
B3÷
B3×
B3(
B3&
C3÷
C3×
C3(
C3&
D3÷
D3×
D3(
D3&
A4÷
A4×
A4(
A4&
B4÷
B4×
B4(
B4&
C4÷
C4×
C4(
C4&
D4÷
D4×
D4(
D4&