Permutations by swapping: Difference between revisions

Content added Content deleted
No edit summary
(Updated both D entries)
Line 238: Line 238:
=={{header|D}}==
=={{header|D}}==
===Iterative Version===
===Iterative Version===
This isn't a Range.
This isn't a Range yet.
{{trans|Python}}
{{trans|Python}}
<lang d>import std.algorithm, std.array, std.typecons, std.range;
<lang d>import std.algorithm, std.array, std.typecons, std.range;
Line 246: Line 246:
alias TResult = Tuple!(int[], int);
alias TResult = Tuple!(int[], int);


int opApply(in int delegate(in ref TResult) dg) {
int opApply(in int delegate(in ref TResult) nothrow dg) nothrow {
int result;
int result;


Line 260: Line 260:
goto END;
goto END;


while (p.canFind!q{ a[1] }) {
while (p.any!q{ a[1] }) {
// Failed to use std.algorithm here, too much complex.
// Failed to use std.algorithm here, too much complex.
auto largest = Int2(-100, -100);
auto largest = Int2(-100, -100);
int i1 = -1;
int i1 = -1;
foreach (immutable i, immutable pi; p) {
foreach (immutable i, immutable pi; p)
if (pi[1]) {
if (pi[1])
if (pi[0] > largest[0]) {
if (pi[0] > largest[0]) {
i1 = i;
i1 = i;
largest = pi;
largest = pi;
}
}
⚫
}
}
immutable n1 = largest[0],
immutable n1 = largest[0],
d1 = largest[1];
d1 = largest[1];
Line 364: Line 362:


===Recursive Version===
===Recursive Version===
Same output.
{{trans|Python}}
{{trans|Python}}
<lang d>import std.algorithm, std.array, std.typecons, std.range;
<lang d>import std.algorithm, std.array, std.typecons, std.range;


auto sPermutations(in int n) /*pure nothrow*/ {
auto sPermutations(in uint n) pure nothrow @safe {
static int[][] sPermu(in int items) /*pure nothrow*/ {
static immutable(int[])[] inner(in int items) pure nothrow @safe {
if (items <= 0)
if (items <= 0)
return [[]];
return [[]];
typeof(return) r;
typeof(return) r;
foreach (immutable i, item; sPermu(items - 1)) {
foreach (immutable i, immutable item; inner(items - 1)) {
//r.put((i % 2 ? iota(cast(int)item.length, -1, -1) :
//r.put((i % 2 ? iota(cast(int)item.length, -1, -1) :
// iota(item.length + 1))
// iota(item.length + 1))
// .map!(i => item[0..i] ~ (items-1) ~ item[i..$]));
// .map!(i => item[0 .. i] ~ (items - 1) ~ item[i .. $]));
immutable f=(in int i)=>item[0..i] ~ (items-1) ~ item[i..$];
immutable f = (in size_t i) pure nothrow @safe =>
item[0 .. i] ~ (items - 1) ~ item[i .. $];
r ~= (i % 2) ?
r ~= (i % 2) ?
iota(cast(int)item.length, -1, -1).map!f.array :
//iota(cast(int)item.length, -1, -1).map!f.array :
iota(item.length + 1).retro.map!f.array :
iota(item.length + 1).map!f.array;
iota(item.length + 1).map!f.array;
}
}
Line 385: Line 384:
}
}


return sPermu(n).zip([1, -1].cycle);
return inner(n).zip([1, -1].cycle);
}
}


void main() {
void main() {
import std.stdio;
import std.stdio;
foreach (immutable n; [3, 4]) {
foreach (immutable n; [2, 3, 4]) {
writefln("\nPermutations and sign of %d items", n);
writefln("Permutations and sign of %d items:", n);
foreach (const tp; n.sPermutations)
foreach (immutable tp; n.sPermutations)
writefln("Perm: %s Sign: %2d", tp[]);
writefln(" %s Sign: %2d", tp[]);
⚫
writeln;
}
}
}</lang>
}</lang>
{{out}}
<pre>Permutations and sign of 2 items:
[1, 0] Sign: 1
[0, 1] Sign: -1

Permutations and sign of 3 items:
[2, 1, 0] Sign: 1
[1, 2, 0] Sign: -1
[1, 0, 2] Sign: 1
[0, 1, 2] Sign: -1
[0, 2, 1] Sign: 1
[2, 0, 1] Sign: -1

Permutations and sign of 4 items:
[3, 2, 1, 0] Sign: 1
[2, 3, 1, 0] Sign: -1
[2, 1, 3, 0] Sign: 1
[2, 1, 0, 3] Sign: -1
[1, 2, 0, 3] Sign: 1
[1, 2, 3, 0] Sign: -1
[1, 3, 2, 0] Sign: 1
[3, 1, 2, 0] Sign: -1
[3, 1, 0, 2] Sign: 1
[1, 3, 0, 2] Sign: -1
[1, 0, 3, 2] Sign: 1
[1, 0, 2, 3] Sign: -1
[0, 1, 2, 3] Sign: 1
[0, 1, 3, 2] Sign: -1
[0, 3, 1, 2] Sign: 1
[3, 0, 1, 2] Sign: -1
[3, 0, 2, 1] Sign: 1
[0, 3, 2, 1] Sign: -1
[0, 2, 3, 1] Sign: 1
[0, 2, 1, 3] Sign: -1
[2, 0, 1, 3] Sign: 1
[2, 0, 3, 1] Sign: -1
[2, 3, 0, 1] Sign: 1
[3, 2, 0, 1] Sign: -1
</pre>


=={{header|Go}}==
=={{header|Go}}==
Retrieved from "https://rosettacode.org/wiki/Permutations_by_swapping"