Partitioning a List Using a List

Scripting Forums AppleScript | Mac OS X
#1

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:


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 :slight_smile:

#2

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:

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.

#3

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.

#4

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.



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
#5

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.


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
#6

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:



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
#7

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.

#8

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.

#9

“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.

#10

Actually it subtracts the partition number from the input number so 4 is partitioned to 1 and 3

#11

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.

#12

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:

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