Enumerate Cartesian Product
27-Sep-2020Comments (0)
Simple Python programs for enumeration of the cartesian product of sets.
Enumeration of Cartesian Product
# Testing
def processTuple(indexes):
global numTuples
numTuples += 1
print(str(indexes) + " #" + str(numTuples))
def main():
global numTuples
numTuples = 0
start_time = time.clock()
test = "cartesianProductForward"
test = "cartesianProductBackward"
test = "cartesianProductForwardGenerator"
print(test)
if test == "cartesianProductForward":
cartesianProductForward([2, 3, 4])
elif test == "cartesianProductBackward":
cartesianProductBackward([2, 3, 4])
elif test == "cartesianProductForwardGenerator":
for indexes in cartesianProductForwardGenerator([2, 3, 4]):
processTuple(indexes)
print(test)
print("numTuples=" + str(numTuples))
print("time[s]=" + str(time.clock() - start_time))
main()
"Forward" Enumeration of Cartesian Product
def cartesianProductForward(dimensions):
# start increasing first index
# indexes[i] runs from 0 to dimensions[i]-1
numDimensions = len(dimensions)
indexes = [0] * numDimensions
processTuple(indexes)
hasNext = True
while hasNext:
# generate new combination
indexes[0] += 1
i = 0
while indexes[i] == dimensions[i]:
# propage carry if any
indexes[i] = 0
i += 1
if i < numDimensions:
indexes[i] += 1
else:
break
if i >= numDimensions:
hasNext = False
else:
processTuple(indexes)
cartesianProductForward
[0, 0, 0] #1
[1, 0, 0] #2
[0, 1, 0] #3
[1, 1, 0] #4
[0, 2, 0] #5
[1, 2, 0] #6
[0, 0, 1] #7
[1, 0, 1] #8
[0, 1, 1] #9
[1, 1, 1] #10
[0, 2, 1] #11
[1, 2, 1] #12
[0, 0, 2] #13
[1, 0, 2] #14
[0, 1, 2] #15
[1, 1, 2] #16
[0, 2, 2] #17
[1, 2, 2] #18
[0, 0, 3] #19
[1, 0, 3] #20
[0, 1, 3] #21
[1, 1, 3] #22
[0, 2, 3] #23
[1, 2, 3] #24
cartesianProductForward
numTuples=24
time[s]=0.0
"Backward" Enumeration of Cartesian Product
def cartesianProductBackward(dimensions):
# start increasing last index
# indexes[i] runs from 0 to dimensions[i]-1
numDimensions = len(dimensions)
indexes = [0] * numDimensions
processTuple(indexes)
hasNext = True
while hasNext:
# generate new combination
i = numDimensions - 1
indexes[i] += 1
while indexes[i] == dimensions[i]:
# propage carry if any
indexes[i] = 0
i -= 1
if i >= 0:
indexes[i] += 1
else:
break
if i < 0:
hasNext = False
else:
processTuple(indexes)
cartesianProductBackward
[0, 0, 0] #1
[0, 0, 1] #2
[0, 0, 2] #3
[0, 0, 3] #4
[0, 1, 0] #5
[0, 1, 1] #6
[0, 1, 2] #7
[0, 1, 3] #8
[0, 2, 0] #9
[0, 2, 1] #10
[0, 2, 2] #11
[0, 2, 3] #12
[1, 0, 0] #13
[1, 0, 1] #14
[1, 0, 2] #15
[1, 0, 3] #16
[1, 1, 0] #17
[1, 1, 1] #18
[1, 1, 2] #19
[1, 1, 3] #20
[1, 2, 0] #21
[1, 2, 1] #22
[1, 2, 2] #23
[1, 2, 3] #24
cartesianProductBackward
numTuples=24
time[s]=0.0
"Forward" Generator of Cartesian Product
def cartesianProductForwardGenerator(dimensions):
# start increasing first index
# indexes[i] runs from 0 to dimensions[i]-1
numDimensions = len(dimensions)
indexes = [0] * numDimensions
yield indexes
hasNext = True
while hasNext:
# generate new combination
indexes[0] += 1
i = 0
while indexes[i] == dimensions[i]:
# propage carry if any
indexes[i] = 0
i += 1
if i < numDimensions:
indexes[i] += 1
else:
break
if i >= numDimensions:
hasNext = False
else:
yield indexes
cartesianProductForwardGenerator
[0, 0, 0] #1
[1, 0, 0] #2
[0, 1, 0] #3
[1, 1, 0] #4
[0, 2, 0] #5
[1, 2, 0] #6
[0, 0, 1] #7
[1, 0, 1] #8
[0, 1, 1] #9
[1, 1, 1] #10
[0, 2, 1] #11
[1, 2, 1] #12
[0, 0, 2] #13
[1, 0, 2] #14
[0, 1, 2] #15
[1, 1, 2] #16
[0, 2, 2] #17
[1, 2, 2] #18
[0, 0, 3] #19
[1, 0, 3] #20
[0, 1, 3] #21
[1, 1, 3] #22
[0, 2, 3] #23
[1, 2, 3] #24
cartesianProductForwardGenerator
numTuples=24
time[s]=0.0
Links
- Cartesian Product of any number of sets (GeeksforGeeks)
- How can I compute a Cartesian product iteratively? (StackOverflow)
- sets - Iterative Cartesian Product in Java
- Generate Combinations in Java (by Chandra Prakash)
New Comment