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. |
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 |
auto sPermutations(in uint n) pure nothrow @safe { |
||
static int[][] |
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; |
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 |
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 |
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(" |
writefln("Permutations and sign of %d items:", n); |
||
foreach ( |
foreach (immutable tp; n.sPermutations) |
||
writefln(" |
writefln(" %s Sign: %2d", tp[]); |
||
⚫ | |||
} |
} |
||
}</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}}== |