Enumerate Cartesian Product

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)

Kommentare