+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: Dividing list into subsets (/thread-30039.html)
Pages:
1
2
Dividing list into subsets - Michael11 - Oct-01-2020
A list is given. You know the number of sticks with which we divide our list into subsets. The rules of division is that the sum of elements in each part should be approximately the same(so that the mininum sum of elements would be as big as possible). Then the programm should print the minimum of that sums.
For example:
Input:
4 (is a number of sticks) (so the list would be divided into three parts)
2 4 4 5 5 8 (the list itself)
Output:
8
Explanation: first we put stick before the first element, another stick at the end of the list(after 8). Then third stick between 4 and 5 , and the fourth between 5 and 8.
Can't think of an algorithm that would perform that task
.
RE: Dividing list into subsets - deanhystad - Oct-01-2020
So the answer is | 2 4 4 | 5 5 | 8 | ?
2+4+4 = 10, 5+5 = 10, 8 = 8
There are some assumptions to be made. The first is that you will always have 3 subsets. Placing two sticks next to each other results in a sum of 0, and that is obviously not going to be the largest subset sum. It is also obvious that there will always be a stick before the first element and after the last element. Three subsets means you only have two sticks to move.
To solve the example list we would start like this:
| 2 | 4 4 5 5 | 8 |
You could do an exhaustive search:
| 2 | 4 4 5 5 | 8 | = 2
| 2 | 4 4 5 | 5 8 | = 2
| 2 | 4 4 | 5 5 8 | = 2
| 2 | 4 | 4 5 5 8 | = 2
| 2 4 | 4 5 5 | 8 | = 6
| 2 4 | 4 5 | 5 8 | = 6
| 2 4 | 4 | 5 5 8 | = 6
| 2 4 4 | 5 5 | 8 | = 8
| 2 4 4 | 5 | 5 8 | = 5
| 2 4 4 5 | 5 | 8 | = 5
This will guarantee you find the best solution, or at least a solution that ties for best. Since there are only 3 subsets even fairly large lists could be processed quite quickly. Play around with the order of the search and multiple algorithms practically leap out at you.
RE: Dividing list into subsets - Michael11 - Oct-02-2020
Yeah,I know,I thought about that solution too at first. The problem lies in the fact that the number of sticks can be bigger,so if we had e.g. 10 sticks and list with length=20, it would take a program forever to complete(maybe I’m wrong). But thank you for your answer and time, anyway!!!)))
RE: Dividing list into subsets - deanhystad - Oct-02-2020
10 sticks with 20 items is still only a few thousand combinations and takes nearly no time to compute. 20 sticks with 100 items is a different proposition. However, most of the partial solutions repeat over and over again and you could probably leverage that to reduce the calculations needed to find a solution.
If you use a recursive solution remember that Python maxes out at 1000 levels of recursion (I think).
RE: Dividing list into subsets - DPaul - Oct-04-2020
Some info is missing.
The proposed list looks very sorted. Is that always the case ?
In case it is, you have a lot more chances to find a simple algorithm.
You might take the group average of the list , that is 9....
Now you start from the left and place the stick when the sum reaches that +/- number.
In this case it might be a coincidence. Do you have a larger example?
Paul
Edit:
I have to refine the previous somewhat: (created a random list with 50+ items, 20 sticks)
I concocted some heuristic that uses the average and the standard deviation.
You start from the left adding items until the sum + sdev > average.
Then you place a stick etc. This is a recursive function, because if you have
sticks left over, deduct 1 from the average and start again.
The tests i ran found a solution within 2 iterations.
To say that this is an algorithm will require some solid proof. :-)
RE: Dividing list into subsets - Michael11 - Oct-04-2020
DPaul,I wrote a piece of code only for 4 sticks. And here it is. It becomes apparent,that as the number of tourists grows the number of inner loops grows as well. So there I can’t yet adapt this code to random values(((As for sums,I assume,we could put them in the list? But as for loops,we should put some code in the function and then call it every time?...
d = list(map(int,input().split()))
sum1 = d[0]
sum2 = d[1]
sum3 = sum(int(d[m]) for m in range(2, int(len(d))))
i=2
k=2
max = 0
for j in range(1,len(d)-1): #(1)we are increasing the distance between the second and the first room
while sum3 != d[len(d)-1]:#(2)(we are increasing the distance between the second and the third room)
sum2+= d[i]
sum3-=d[i]
i+=1
a = min(sum1,sum2,sum3)
if max < a:
max=min(sum1,sum2,sum3)
sum1+=d[j]
i = k+1
sum2=d[i-1]
sum3 = sum(int(d[m]) for m in range(i, int(len(d))))
k += 1
print(max)
Unfortunately,the list is not always sorted
RE: Dividing list into subsets - DPaul - Oct-04-2020
1) pls put your code in python brackets, so we can see indentation.
2) Suddenly we are dealing with rooms, not sticks, ?
3) What is the starting list ?
Disregard my sorting comment. I have a result in 1 or 2 iterations (150 numbers, 25 sticks)
even without sorting.
Paul
RE: Dividing list into subsets - Katenn - Oct-04-2020
I just mixed up two very similar tasks. We're still dealing with sticks. Here is the code for 4 and 5 sticks
if t ==4:
max = 0
sum1 = 0
sum2=0
sum3=0
for h in range(len(d)-1):
for b in range(1,len(d)-1):
sum1 = sum(int(d[m]) for m in range(0,h+1))
sum2 = sum(int(d[m]) for m in range(h+1,b+1))
sum3 = sum(int(d[m]) for m in range(b+1,len(d)))
if max < min(sum1, sum2, sum3):
max = min(sum1, sum2, sum3)
elif t == 5:
max = 0
sum1 = 0
sum2 = 0
sum3 = 0
sum4 = 0
for k in range(len(d)-1):
for l in range(1,len(d)-1):
for m in range(2,len(d)-1):
sum1 = sum(int(d[m]) for m in range(0, k+1))
sum2 = sum(int(d[m]) for m in range(k+1, l+1))
sum3 = sum(int(d[m]) for m in range(l+1,m+1 ))
sum4 = sum(int(d[m]) for m in range(m+1, int(len(d))))
if max < min(sum1, sum2, sum3,sum4):
max = min(sum1, sum2, sum3,sum4)
print(max)
RE: Dividing list into subsets - DPaul - Oct-05-2020
I'm afraid i am totally lost here.
Not only has TS changed his/her name,
the piece of code presented seems to be an extract of someting bigger?
We are happy to help but you must make it easier for us :-)
Paul
RE: Dividing list into subsets - deanhystad - Dec-11-2020
I guess this question has been bugging me for a while because when I saw an unrelated post about optimization the answer to this question popped into my head. The solution is to make an initial guess at a solution and then adjust the guess to find a better solution. Kind of like Newtons method for finding local min or max.
For a first guess I break up the bag (collection of all numbers) into evenly sized groups. I tried other grouping ideas but this gave the best results for a random group of numbers.
sizes = [len(bag)//count] * count sizes[-1] = len(bag) - sizes[0] * (count-1)Subsequent guesses remove a number from the highest value group and add a number to the lowest value group.
sizes[score.index(min(score))] += 1 sizes[score.index(max(score))] -= 1The tricky part was deciding when the best solution had been found. At first I quit when my guess resulted in a worse score. This didn't work. Sometimes more than two groups have to be adjusted to get a better score with an intermediate step resulting in a lower score.
Running the code with limited guesses and printing out each guess I noticed the guesses eventually start to loop. Usually the program starts bouncing back and forth between the last two guesses, but it can also end up in a cycle. Either way we already calculated the best solution and all we need to do is stop guessing. To identify when the code has entered a loop I retain a log of the previous guesses. If I already made a guess that means I also already made the next guess and all future guesses.
if sizes in prev_sizes:
return list(groups(bag, best_sizes))This is the code.import random
def sticks(bag, count):
'''Split bag into count groups. Find the grouping that results
in the highest minimum group score. Group score is the sum of
numbers in the group.
'''
def groups(bag, sizes):
"""Split bag up into groups based on sizes"""
i = 1
for s in sizes:
yield bag[i:i+s]
i += s
count -= 1 # Number of groups
sticks.guesses = 0 # Keep track of how many guesses
# Make an initial guess
sizes = [len(bag)//count] * count
sizes[-1] = len(bag) - sizes[0] * (count-1)
best_score = 0
best_sizes = sizes
prev_sizes = [] # Keep track of previous guesses
while True:
sticks.guesses += 1
# Have we tried this guess before? If so we have
# already found the best solution.
if sizes in prev_sizes:
return list(groups(bag, best_sizes))
prev_sizes.append(sizes.copy())
# Is this better than our previous best?
score = [sum(group) for group in groups(bag, sizes)]
new_score = min(score)
if new_score > best_score:
best_score = new_score
best_sizes = prev_sizes[-1]
# Try to make a better guess by removing a number from
# the highest group and adding a number to the lowest group.
sizes[score.index(min(score))] += 1
sizes[score.index(max(score))] -= 1
bag = random.choices(range(1, 101), k=20)
result = sticks(bag, 6)
score = [sum(group) for group in result]
print('Groups', result)
print('Score', min(score), ':', score)
print('Guesses', sticks.guesses)For a comparison I also wrote a program that calculates the score for every possible combination of sizes and picked the best score. For 6 sticks and a bag of 20 numbers this is 3876 guesses. The code above usually gets the best solution in 5 guesses.