Ceylon Web Runner: test27012018

main.ceylon

import ceylon.numeric.integer { smallest }

shared void run() {
	value summands = map<Data, Count> {
		1->2, 2->1, 3->3, 5->1, 7->2, 9->1, 11->4, 17->2, 19->1
	};
	value intendedSum = 44;
	value partitions = partitionsWithSum(intendedSum, summands).sequence();
    print("\n``intendedSum`` has ``partitions.size`` partitions:");
	partitions.each(print);
}

shared alias Data => Integer;
shared alias Index => Integer;
shared alias Count => Integer;
shared alias Partition => [Data*];
shared alias Characteristic => [Count*];
shared alias Multiplicity => Data->Count;
shared alias Multiset => Map<Data, Count>;

shared class Status of equal | tooSmall | unknown {
	shared actual String string;
	shared new equal { string = "="; }
	shared new tooSmall { string = "<"; }
	shared new unknown { string = "?"; }
}
shared class SubsetTraversal(elemCount, maxAllowedCount, delta) {
	Integer elemCount;
	Count maxAllowedCount(Index elemIndex);
	Status delta(Index elemIndex, Count count, Characteristic got());
	
	value current = Array.ofSize(elemCount, 0);
	variable Status|Finished status = Status.unknown;
	variable value index = -1;
	
	Characteristic() got = current.sequence;
	
	shared Boolean advance() {
		// trace
		print("``current.mapElements((i, x) => if (i > index) then "*" else x)``\t``status``");
		// trace end
		switch (status)
		case (finished) { return false; }
		case (Status.unknown) {
			index += 1;
			value startCount = maxAllowedCount(index);
			current[index] = startCount;
			status = delta(index, startCount, got);
		}
		case (Status.equal) {
			assert (exists count = current[index], count > 0);
			current[index] = count - 1;
			status = delta(index, -1, got);
		}
		case (Status.tooSmall) {
			assert (exists lastCount = current[index]);
			current[index] = 0;
			if (lastCount != 0) {
				delta(index, -lastCount, got);
			}
			index -= 1;
			while (exists count = current[index]) {
				if (count == 0) {
					index -= 1;
					continue;
				}
				current[index] = count - 1;
				status = delta(index, -1, got);
				break;
			}
			if (index == -1) {
				status = finished;
				return false;
			}
		}
		return true;
	}
}

shared {Partition*} partitionsWithSum(Data intendedSum, Multiset summands) {
	"Summands should be positive."
	assert (summands.keys.every((x) => x > 0));
	if (intendedSum < 0) { return {}; }
	else if (intendedSum == 0) { return {[]}; }
	
	value summands2 = summands.sort(byDecreasing(Multiplicity.key)).sequence();
	value partialSums = summands2.collect((x->m) => x * m).
			reversed.scan(0)(plus).sequence().reversed;
	
	function partitionFromCharacteristic(Characteristic c) =>
		zipPairs(summands2, c).flatMap(([x->_, m]) => {x}.repeat(m)).sequence();
	
	return object satisfies {Partition*} {
		iterator() => object satisfies Iterator<Partition> {
			variable Data sumLeft = intendedSum;
			variable Characteristic? newCharacteristic = null;
			value t = SubsetTraversal {
				elemCount = summands2.size;
				function maxAllowedCount(Index elemIndex) {
					assert (exists x->m = summands2[elemIndex]);
					return smallest(m, sumLeft / x);
				}
				function delta(Index elemIndex, Count count, Characteristic got()) {
					assert (exists x = summands2[elemIndex]?.key);
					assert (exists summandsLeft = partialSums[elemIndex + 1]);
					sumLeft -= x * count;
					if (summandsLeft < sumLeft) { return Status.tooSmall; }
					if (sumLeft == 0) {
						newCharacteristic = got();
						return Status.equal;
					}
					return Status.unknown;
				}
			};
			
			shared actual Partition|Finished next() {
				while (t.advance()) {
					if (exists ch = newCharacteristic) {
						newCharacteristic = null;
						return partitionFromCharacteristic(ch);
					}
				}
				return finished;
			}
		};
	};
}

module.ceylon

module web_ide_script "1.0.0" {
	import ceylon.numeric "1.3.3";
}

Click here to run this code online