Ordered partitions: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: future-proof for 5.36) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (4 intermediate revisions by 2 users not shown) | |||
Line 1,389:
Here, on the right hand side we form 0 1 0 1 2 3 4 5, count how many things are in it (8), form 0 1 2 3 4 5 6 7 from that and then remove 0 1 (the values in the left argument) leaving us with 2 3 4 5 6 7. Meanwhile, on the left side, keep our left argument intact and use the indices in the remaining boxes to select from the right argument. In theoretical terms this is not particularly efficient, but we are working with very short lists here (because otherwise we run out of memory for the result as a whole), so the actual cost is trivial. Also note that sequential loops tend to be faster than nested loops (though we do get the effect of a nested loop, here - and that was the theoretical inefficiency).
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class OrderedPartitions {
public static void main(String[] aArgs) {
List<Integer> sizes = ( aArgs == null || aArgs.length == 0 ) ?
List.of( 2, 0, 2 ) : Arrays.stream(aArgs).map( s -> Integer.valueOf(s) ).toList();
System.out.println("Partitions for " + sizes + ":");
final int total = sizes.stream().reduce(0, Integer::sum);
List<Integer> permutation = IntStream.rangeClosed(1, total).boxed().collect(Collectors.toList());
while ( hasNextPermutation(permutation) ) {
List<List<Integer>> partition = new ArrayList<List<Integer>>();
int sum = 0;
boolean isValid = true;
for ( int size : sizes ) {
List<Integer> subList = permutation.subList(sum, sum + size);
if ( ! isIncreasing(subList) ) {
isValid = false;
break;
}
partition.add(subList);
sum += size;
}
if ( isValid ) {
System.out.println(" ".repeat(4) + partition);
}
}
}
private static boolean hasNextPermutation(List<Integer> aPerm) {
final int lastIndex = aPerm.size() - 1;
int i = lastIndex;
while ( i > 0 && aPerm.get(i - 1) >= aPerm.get(i) ) {
i--;
}
if ( i <= 0 ) {
return false;
}
int j = lastIndex;
while ( aPerm.get(j) <= aPerm.get(i - 1) ) {
j--;
}
swap(aPerm, i - 1, j);
j = lastIndex;
while ( i < j ) {
swap(aPerm, i++, j--);
}
return true;
}
private static boolean isIncreasing(List<Integer> aList) {
return aList.stream().sorted().toList().equals(aList);
}
private static void swap(List<Integer> aList, int aOne, int aTwo) {
final int temp = aList.get(aOne);
aList.set(aOne, aList.get(aTwo));
aList.set(aTwo, temp);
}
}
</syntaxhighlight>
{{ out }}
<pre>
Partitions for [2, 0, 2]:
[[1, 3], [], [2, 4]]
[[1, 4], [], [2, 3]]
[[2, 3], [], [1, 4]]
[[2, 4], [], [1, 3]]
[[3, 4], [], [1, 2]]
</pre>
=={{header|JavaScript}}==
Line 2,555 ⟶ 2,642:
gather {
s.combinations(args[0], { |*c|
part(s - c, args.
})
}
Line 2,685 ⟶ 2,772:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var genPart // recursive so predeclare
| |||