Ordered partitions: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (5 intermediate revisions by 3 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}}==
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 1,882 ⟶ 1,969:
=={{header|Perl}}==
===Threaded Generator Method===
generators or Go's channels by using Thread::Queue. Granted, this is horribly inefficient, with constantly creating and killing threads and whatnot (every time a partition is created, a thread is made to produce the next partition, so thousands if not millions of threads live and die, depending on the problem size). But algorithms are often more naturally expressed in a coroutine manner -- for this example, "making a new partition" and "picking elements for a partition" can be done in separate recursions cleanly if so desired. It's about 20 times slower than the next code example, so there.
<syntaxhighlight lang="perl">use
use warnings;
use Thread 'async';
use Thread::Queue;
Line 1,911 ⟶ 2,001:
};
$q =
(async{ &$gen; # start the main work load
$q->enqueue(undef) # signal that there's no more data
Line 1,927 ⟶ 2,017:
print "@$a | @$b | @$rb\n";
}
}</syntaxhighlight>
▲}
▲</syntaxhighlight>
{{trans|Raku}}
<syntaxhighlight lang="perl">use
use warnings;
use List::Util 1.33 qw(sum pairmap);
sub partition {
Line 2,551 ⟶ 2,642:
gather {
s.combinations(args[0], { |*c|
part(s - c, args.
})
}
Line 2,681 ⟶ 2,772:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var genPart // recursive so predeclare
| |||