You are not logged in.
Hi MacScripters,
I'm working on a project which requires me to partition a list using a list. Here's an example:
Example input:
list to partition by = {4, 1, 9, 6, 2, 2}
list to partition = {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1}
the sum of each list will always be equal
Example output:
output list = {{1,1,1,1}, {1}, {2,2,2,3}, {3,3}, {1,1}, {1,1}}
I created a solution which works, but I'm very new to algorithms, and was curious if there's a better solution?
Here's my current function:
Applescript:
set partition1 to {4, 1, 9, 6, 2, 2}
set input1 to {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1}
set output1 to {}
partitionList(input1, output1, partition1)
on partitionList(inputList, outputList, partitionBy)
set partitionStartIndex to 1
set inputStartIndex to 1
set inputEndIndex to 1
repeat (count of partitionBy) times
set currentPartitionItem to item partitionStartIndex of partitionBy
set currentInputItem to item inputStartIndex of inputList
if currentInputItem < currentPartitionItem then
set sum to currentInputItem
repeat while sum < currentPartitionItem
set nextInputItem to item (inputEndIndex + 1) of inputList
set sum to sum + nextInputItem
set inputEndIndex to inputEndIndex + 1
end repeat
copy (items inputStartIndex thru inputEndIndex of inputList as list) to end of outputList
else
copy (currentInputItem as list) to end of outputList
end if
set partitionStartIndex to partitionStartIndex + 1
set inputEndIndex to inputEndIndex + 1
set inputStartIndex to inputEndIndex
end repeat
return outputList
end partitionList
Any thoughts regarding efficiency or redundancy that I probably overlooked would be welcome
Last edited by GEC1227 (2021-03-27 05:35:36 pm)
Offline
GEC1227. I tested your script, which works well.
Your script seems to contain two related assumptions. The first--which you note--is that the sum of the numbers in the partition list and the sum of the numbers in the input list are equal. The second is that the sum of consecutive numbers in the input list exactly equal consecutive individual numbers in the partition list. For example, your script breaks if the lists are:
set partition1 to {4, 2, 8, 6, 2, 2} -- 24 total
set input1 to {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1} -- 24 total
I tried to rewrite your script to significantly improve it in some way without success, and my final effort takes the same general approach as your script. FWIW:
Applescript:
set partition1 to {4, 1, 9, 6, 2, 2}
set input1 to {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1}
partitionList(input1, partition1)
on partitionList(inputList, partitionBy)
set outputList to {}
repeat with i from 1 to (count partitionBy)
set runningTotal to 0
set tempList to {}
repeat with j from 1 to (count inputList)
set inputNumber to item j of inputList
set runningTotal to runningTotal + inputNumber
if runningTotal = (item i of partitionBy) then
set end of outputList to (tempList & inputNumber)
if j < (count inputList) then set inputList to items (j + 1) thru -1 of inputList
exit repeat
else
set end of tempList to inputNumber
end if
end repeat
end repeat
return outputList -- {{1, 1, 1, 1}, {1}, {2, 2, 2, 3}, {3, 3}, {1, 1}, {1, 1}}
end partitionList
I'll look forward to suggestions from other forum members.
Last edited by peavine (2021-03-29 07:18:44 am)
2018 Mac mini - macOS Catalina
Offline
Thanks for your thoughts, peavine!
I should have written in my original post that in addition to the sum of each list always being equal, the sum of consecutive numbers in the input list will also always be equal to the value of consecutive numbers in the partition list, at least in the script I'm working on.
The condition which breaks the function is a limitation which is VERY good for me to know about, especially if I ever reuse it--thank you for bringing it to my attention.
As you wrote, I'm looking forward to learning more from other forum members too.
*Update to this reply: I was incorrect. The data will not always be equal, so the example you provided could happen during use and has been causing problems during testing. I'll try to create a solution, which, if successful, I'll be sure to share.
Last edited by GEC1227 (2021-03-30 08:14:39 pm)
Offline
Here's an idea for a solution to the problem discussed above:
The idea is to check if the "runningTotal" variable is greater than the "partitionBy" variable, if it is, that means there's a problem. A possible solution would be for an item to borrow from its neighbor.
The solution works for this example, but the code is crude in its current form, as it has not been developed to account for all situations--the same logic could probably be applied to subsequent iterations though.
Applescript:
set partitionBy1 to {4, 2, 8, 6, 2, 2}
set inputList1 to {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1}
set partitionedList to {}
partitionList(inputList1, partitionBy1)
on partitionList(inputList, partitionBy)
set partitionedList to {}
repeat with i from 1 to (count partitionBy)
set partitionNumber to item i of partitionBy
set runningTotal to 0
set intermediateList to {}
repeat with j from 1 to ((count inputList) - 1)
set inputNumber to item j of inputList
set runningTotal to runningTotal + inputNumber
if runningTotal = partitionNumber then
set end of partitionedList to (intermediateList & inputNumber)
set inputList to items (j + 1) thru -1 of inputList
exit repeat
else if runningTotal > partitionNumber then
set item j of inputList to (inputNumber - 1)
set inputList to (inputNumber - 1) & inputList
set end of partitionedList to (intermediateList & (inputNumber - 1))
set inputList to items (j + 1) thru -1 of inputList
exit repeat
else
set end of intermediateList to inputNumber
end if
end repeat
end repeat
set end of partitionedList to intermediateList & item -1 of inputList
return partitionedList
end partitionList
Offline
Hi, GEC1227,
Your original script is very effective in terms of efficiency. As for redundancy, I hardly see it either. Unless the additional outputList can be removed.
As for correcting errors when specifying 2 lists, here it is better to throw an error than to artificially correct it on runtime.
Applescript:
set partition1 to {4, 1, 9, 6, 2, 2}
set input1 to {1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1}
my partitionList(input1, partition1)
on partitionList(inputList, partitionBy)
set partitionStartIndex to 1
set inputStartIndex to 1
set inputEndIndex to 1
repeat (count of partitionBy) times
set currentPartitionItem to item partitionStartIndex of partitionBy
set currentInputItem to item inputStartIndex of inputList
if currentInputItem < currentPartitionItem then
set sum to currentInputItem
repeat while sum < currentPartitionItem
set nextInputItem to item (inputEndIndex + 1) of inputList
set sum to sum + nextInputItem
set inputEndIndex to inputEndIndex + 1
end repeat
if sum > currentPartitionItem then error "Partition list doesn't correspond to Input list"
set item partitionStartIndex of partitionBy to (items inputStartIndex thru inputEndIndex of inputList) as list
else
set item partitionStartIndex of partitionBy to (currentInputItem as list)
end if
set partitionStartIndex to partitionStartIndex + 1
set inputEndIndex to inputEndIndex + 1
set inputStartIndex to inputEndIndex
end repeat
return partitionBy
end partitionList
Last edited by KniazidisR (2021-03-31 11:15:02 am)
Model: MacBook Pro
OS X: Catalina 10.15.4
Web Browser: Safari 13.1
Ram: 4 GB
Offline
Thanks for your thoughts, KniazidisR!
In regards to the logic of the algorithm itself, I received a second opinion from Stack Overflow and thought i would share it here, just in case it helps someone in the future.
Here's the revised solution:
Applescript:
set partitionByExample to {4, 1, 9, 1, 3, 6, 2, 2}
set inputListExample to {1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 3, 3, 1, 1, 1, 1}
partitionList(inputListExample, partitionByExample)
on partitionList(inputList, partitionBy)
set partitionedList to {}
set j to 1
set overflow to false
repeat with i from 1 to (count partitionBy)
set partitionNumber to item i of partitionBy
set runningTotal to 0
set intermediateList to {}
repeat while j < (count inputList)
if overflow then
set overflow to false
else
set inputNumber to item j of inputList
end if
set runningTotal to runningTotal + inputNumber
if runningTotal = partitionNumber then
set end of partitionedList to (intermediateList & inputNumber)
set j to j + 1
exit repeat
else if runningTotal > partitionNumber then
set end of partitionedList to {partitionNumber}
set overflow to true
set inputNumber to runningTotal - partitionNumber
exit repeat
else
set end of intermediateList to inputNumber
set j to j + 1
end if
end repeat
end repeat
set end of partitionedList to intermediateList & item -1 of inputList
return partitionedList
end partitionList
Offline
Hi. If I understand correctly, it seems that you're feeding the code in post #6 an impossible series; e.g. it returns partition {1}, given input 4, and then it uses a 3 that was already played.
Offline
FWIW, the script in post 6 seems to employ a carry-forward strategy. When runningTotal exceeds partitionNumber, a new input number is created in an amount equal to the overage. If that's what the OP wants then this script seems a workable solution.
In the example given by Marc Anthony, the input number is 4 and the partition number is 1. The script adds {1} to the output list and then creates a new input number of 3.
2018 Mac mini - macOS Catalina
Offline
"Carry-forward" is a good way of describing it, peavine. And yes, this solution has thus far been working in the application it was created for.
Offline
In the example given by Marc Anthony, the input number is 4 and the partition number is 1. The script adds {1} to the output list and then creates a new input number of 3.
Actually it subtracts the partition number from the input number so 4 is partitioned to 1 and 3
regards
Stefan
Offline
peavine wrote:
In the example given by Marc Anthony, the input number is 4 and the partition number is 1. The script adds {1} to the output list and then creates a new input number of 3.
Actually it subtracts the partition number from the input number so 4 is partitioned to 1 and 3
Stefan. I don't believe that's correct.
The script encounters input number 4 and partition number 1. It adds {1} to the output list and creates a new input number of 3. In the next repeat loop, the carried-forward input number is 3 and the partition number is also 3. So, {3} is added to the output list. This may make it appear that 4 is partitioned into 1 and 3 but I don't believe that is what's happening.
To illustrate this point, assume that the next partition number is 2 rather than 3:
set partitionByExample to {4, 1, 9, 1, 2, 6, 2, 2}
set inputListExample to {1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 3, 3, 1, 1, 1}
In this case, the script encounters input number 4 and partition number 1. It adds {1} to the output list and creates a new input number of 3. In the next repeat loop, the carried-forward input number is 3 and the partition number is 2. So {2} is added to the output list. This would seem to confirm that 4 is not partitioned into 1 and 3.
Last edited by peavine (2021-04-09 07:42:59 am)
2018 Mac mini - macOS Catalina
Offline
There appears to be an error (or at least an inconsistency) in the script in post 6. By way of illustration, if the input and partition lists are:
set partitionByExample to {1, 2, 6, 2, 2}
set inputListExample to {4, 3, 3, 1, 1, 1}
The script in post 6 returns the first of the following and--based on my understanding of the OP's requirements--should return the second of the following:
{{1}, {2}, {6}, {1, 1}, {1, 1}}
{{1}, {2}, {1, 3, 2}, {1, 1}, {1, 1}}
In limited testing, the following revised script appears to work correctly:
Applescript:
set partitionByExample to {1, 2, 6, 2, 2}
set inputListExample to {4, 3, 3, 1, 1, 1}
partitionList(inputListExample, partitionByExample)
on partitionList(inputList, partitionBy)
set partitionedList to {}
set overflow to 0
set j to 1
repeat with i from 1 to (count partitionBy)
set partitionNumber to item i of partitionBy
set runningTotal to 0
set intermediateList to {}
repeat while j ≤ (count inputList)
if overflow > 0 then
set overflow to 0
else
set inputNumber to item j of inputList
end if
set runningTotal to runningTotal + inputNumber
if runningTotal = partitionNumber then
set end of partitionedList to (intermediateList & inputNumber)
set j to j + 1
exit repeat
else if runningTotal > partitionNumber then
set overflow to (runningTotal - partitionNumber)
set end of partitionedList to (intermediateList & (inputNumber - overflow))
set inputNumber to overflow
exit repeat
else
set end of intermediateList to inputNumber
set j to j + 1
end if
end repeat
end repeat
return partitionedList --> {{1}, {2}, {1, 3, 2}, {1, 1}, {1, 1}}
end partitionList
Last edited by peavine (2021-04-13 07:15:52 am)
2018 Mac mini - macOS Catalina
Offline