public
Last active

  • Download Gist
SubsetSum.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
# Finds the all potential sums for some 3-space configuration of x y z dimensions
# with values corresponding to inputArray, stacked in precedence of x, y, z
def sumFinder(x, y, z, inputArray):
 
foundZeroSum = False
 
# Checks all potential sets starting with a single value
for i in range(0, len(inputArray)):
xSum = list()
ySum = list()
zSum = list()
 
xSum.append(inputArray[i])
ySum.append(inputArray[i])
zSum.append(inputArray[i])
 
# Walk all three dimensions, adding elements one by one
# X dimension
for j in range(1, x - (i % x + 1)):
if sum(xSum) == 0:
foundZeroSum = True
print(xSum)
 
xSum.append(inputArray[i + j])
# Y dimension
for j in range(1, y - (int(i / y) + 1)):
# The length check is to ensure no repeat lists of single 0s
if sum(ySum) == 0 and len(ySum) != 1:
foundZeroSum = True
print(ySum)
 
ySum.append(inputArray[i + x * j])
 
# Z dimension
for j in range(1, z - (int(i / (x * y)) + 1)):
if sum(zSum) == 0 and len(zSum) != 1:
foundZeroSum = True
print(zSum)
 
zSum.append(inputArray[i + j * x * y])
 
# If we haven't found anything, oh well.
if not foundZeroSum:
print("No subsets sum to 0")
 
# Calling function
def sumCaller():
x = 0
y = 0
z = 0
cubeArray = list()
 
# Grabs the dimensions from the user
inputString = input("Enter the dimensions: ").split()
x = int(inputString[0])
y = int(inputString[1])
z = int(inputString[2])
 
# Nicely converts the user's string into an integer array
cubeArray = [int(i) for i in input("Enter the values: ").split()]
 
# Checks for proper number of values
if len(cubeArray) != x * y * z:
print("Invalid dimensions for input values")
return False
 
sumFinder(x, y, z, cubeArray)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.