EN → DE A-AA+ Sitemap Search

## Enumerate Cartesian Product

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
``````