Tuesday, May 11, 2021

#1 2021-03-27 05:34:06 pm

GEC1227
Member
Registered: 2020-01-22
Posts: 21

Partitioning a List Using a List

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 smile

Last edited by GEC1227 (2021-03-27 05:35:36 pm)

Offline

 

#2 2021-03-28 08:25:18 am

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 872

Re: Partitioning a List Using a List

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

 

#3 2021-03-28 12:19:17 pm

GEC1227
Member
Registered: 2020-01-22
Posts: 21

Re: Partitioning a List Using a List

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

 

#4 2021-03-30 10:38:29 pm

GEC1227
Member
Registered: 2020-01-22
Posts: 21

Re: Partitioning a List Using a List

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

 

#5 2021-03-31 11:05:32 am

KniazidisR
Member
From:: Greece
Registered: 2019-03-03
Posts: 1797

Re: Partitioning a List Using a List

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 14.1
Ram: 4 GB

Offline

 

#6 2021-04-06 11:27:03 am

GEC1227
Member
Registered: 2020-01-22
Posts: 21

Re: Partitioning a List Using a List

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

 

#7 2021-04-06 05:21:21 pm

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 1017

Re: Partitioning a List Using a List

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

 

#8 2021-04-07 07:43:03 am

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 872

Re: Partitioning a List Using a List

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

 

#9 2021-04-07 08:52:01 pm

GEC1227
Member
Registered: 2020-01-22
Posts: 21

Re: Partitioning a List Using a List

"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

 

#10 2021-04-08 02:19:16 am

StefanK
Member
From:: St. Gallen, Switzerland
Registered: 2006-10-21
Posts: 11746
Website

Re: Partitioning a List Using a List

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


regards

Stefan

Offline

 

#11 2021-04-08 09:34:24 am

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 872

Re: Partitioning a List Using a List

StefanK wrote:
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

 

#12 2021-04-08 07:15:14 pm

peavine
Member
From:: Prescott, Arizona
Registered: 2018-09-04
Posts: 872

Re: Partitioning a List Using a List

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

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)