0

I'm making a practice program in Python to calculate all the different weights I can put on the rack, with a given set of plates.

def Weights(t=1,f=1,tn=1,tf=1,thf=1,ff=1,b=45):

  Max=b+5*t+10*f+20*tn+50*tf+70*thf+90*ff
  Poss=range(b,Max+1,5)

  ts=(list((i*5 for i in range(0,t+1))))
  fs=(list((i*10 for i in range(0,f+1))))
  tns=(list((i*20 for i in range(0,tn+1))))
  tfs=(list((i*50 for i in range(0,tf+1))))
  thfs=(list((i*70 for i in range(0,thf+1))))
  ffs=(list((i*90 for i in range(0,ff+1))))

Weights()

This leaves me with 6 lists. To get all the combos, I need to add up one element of a list with one element of each other list. At this point, it's clearly a linear algebra problem, I just don't know how to express this in Python, especially because I don't want to use plugins (No NumPy)

Improve this question
1
  • You use words like "rack" and "plates" when talking about your code and yet they appear nowhere in your code. It is therefore very hard to understand whatever you are talking about. Commented Mar 17, 2017 at 1:42

2 Answers 2

Reset to default
3

To get all the combos, I need to add up one element of a list with one element of each other list.

It sounds like you want itertools.product. To simplify the example, let's just take three of your seven terms (but it's trivial to pass more, or fewer, arguments into product):

import itertools

b = [45]  # I assume this represents the "bar" and that it's not optional
ts = [0, 5, 10, 15]
fs = [0, 10]

combos = itertools.product(b, ts, fs)
for combo in combos: print(list(combo))

prints the following:

[45, 0, 0]
[45, 0, 10]
[45, 5, 0]
[45, 5, 10]
[45, 10, 0]
[45, 10, 10]
[45, 15, 0]
[45, 15, 10]

...which sounds like what you want when you refer to "all the combos".

To get the sum of each, it can all be done in one line:

totals = [sum(combo) for combo in itertools.product(b, ts, fs)]

Here's a possible flexible way of parameterizing the function:

import itertools

def PossibleWeights(*weights):
    return list(itertools.product(*[[weightset] if isinstance(weightset, (int, float)) else [sum(weightset[:i]) for i in range(len(weightset)+1)] for weightset in weights]))

When you call, say, PossibleWeights( 45, [10]*2, [5]*3 ) the call itself makes it explicit (and readable) that there is one compulsory 45-pound weight, two possible 10-pound weights, and three possible 5-pound weights. You have complete flexibility as to how many such arguments you pass and what their values are.

You could then use a dict to associate each total weight with the combo used to achieve it (incidentally removing duplicate totals, where more than one combo adds up to the same total):

d = {}
for combo in PossibleWeights( 45, [10]*2, [5]*3 ):
    d[sum(combo)] = combo

...and then pretty-print the result:

for total, combo in sorted(d.items()):
    print('sum(%r) = %r' % (combo, total))

Output:

sum((45, 0, 0)) = 45
sum((45, 0, 5)) = 50
sum((45, 10, 0)) = 55
sum((45, 10, 5)) = 60
sum((45, 20, 0)) = 65
sum((45, 20, 5)) = 70
sum((45, 20, 10)) = 75
sum((45, 20, 15)) = 80

BTW: if you want to achieve each total using the minimum number of plates, make sure you're passing heavier plates before lighter plates in your call to PossibleWeights, as in the example above.

Balancing both sides of the bar is left as an exercise for the reader ;-)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

I think your approach is wrong and also you signature is bad design: what if you have other than 7 different kinds of weights? I think input as list of tuples (weight, max_number) is more appropriate. And when you start thinking in such terms you understand that "cross-joining" 7 lists is also wrong approach. What you want is to have one list of all simple weights and than get the power set i.e. all subsets. Rosetta Code has a few nice implementations of power set in Python. I particularly like this one because it doesn't force generation of whole power-set in memory which might be an issue:

def powersequence(val):
    ''' Generate a 'powerset' for sequence types that are indexable by integers.
        Uses a binary count to enumerate the members and returns a list

        Examples:
            >>> powersequence('STR')   # String
            ['', 'S', 'T', 'ST', 'R', 'SR', 'TR', 'STR']
            >>> powersequence([0,1,2]) # List
            [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]
            >>> powersequence((3,4,5)) # Tuple
            [(), (3,), (4,), (3, 4), (5,), (3, 5), (4, 5), (3, 4, 5)]
            >>> 
    '''
    vtype = type(val); vlen = len(val); vrange = range(vlen)
    return [ reduce( lambda x,y: x+y, (val[i:i+1] for i in vrange if 2**i & n), vtype())
             for n in range(2**vlen) ]

Or you can build one using itertools powerset recipe which is in practice faster (thanks to umutto)

def powersequence(val):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

So the algorithm is:

  1. Build single list of all simple weights (join of your ts, fs, ...)
  2. Use powersequence to generate powerset
  3. Sum all items in each sub-set
  4. Push results to set to filter for uniqueness 
def all_weights(ws):
    simpleWeights = [0] # add 0 just one time
    for (w, c) in ws:
        simpleWeights = simpleWeights + [w] * c
    allWeights = (sum(subset) for subset in powersequence(simpleWeights))
    return set(allWeights)  # filter uniqueness


all = all_weights([(1, 1), (5, 1), (10, 1), (20, 1), (50, 1), (70, 1), (90, 1)])
for w in all:
    print(w)

Note that uniqueness condition forces materialization of whole collection into memory so might be a limiting factor of the size of the problem this code can solve.

Update

Actually jez is right: doing product of lists by coins will be significantly faster then iterating through powersequence of joined lists 

def all_weights(ws):
    simpleWeights = []
    for (w, c) in ws:
        simpleWeights.append(list((i * w for i in range(0, c + 1))))

    allWeights = (sum(subset) for subset in itertools.product(*simpleWeights)) # note "*" before simpleWeights!
    return set(allWeights)  # filter uniqueness
Improve this answer

4 Comments

You could shorten and probably optimize the powersequence function by using itertools powerset recipe (chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))
@umutto, Yes, this is shorter, but I doubt that this is actually an optimization. I think generation of all subsets in their natural numbering order migth be faster than generating them in order of increasing size using combinations inside.
@umutto, I did some tests and to my suprise itertools-based implementation is much faster (like an order of magnitude faster). Now I think this should mainly be because itertools are implemented in C. Thanks anyway for pointing this out.
@SerGr yeah I was benchmarking them now, glad it was helpful.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.