Permutations: Difference between revisions

Content added Content deleted
(+ tag in Faster Lazy Version)
(Fixed lazy D version)
Line 852: Line 852:
[3, 2, 1]</pre>
[3, 2, 1]</pre>
===Faster Lazy Version===
===Faster Lazy Version===
{{incorrect|D|This version is designed to sort indexes only.}}
Compiled with <code>-version=permutations2_main</code> produces the same output:
Compiled with <code>-version=permutations2_main</code> produces the same output:
<lang d>import std.algorithm, std.exception;
<lang d>import std.algorithm, std.conv, std.traits;


struct Permutations(bool doCopy=true, T) {
struct Permutations(bool doCopy=true, T) if (isMutable!T) {
private immutable size_t num;
private immutable size_t num;
private T[] items;
private T[] items;
private uint[31] indexes;
private ulong tot;
private ulong tot;


this (/*in*/ T[] items) pure nothrow
this (/*in*/ T[] items) /*pure*/ nothrow
in {
in {
enforce(items.length > 0,
static immutable string L = text(indexes.length); // impure
"Permutations: items.length must be > 0");
assert(items.length >= 0 && items.length <= indexes.length,
"Permutations: items.length must be >= 0 && < " ~ L);
} body {
} body {
static ulong factorial(in uint n) pure nothrow {
static ulong factorial(in uint n) pure nothrow {
Line 875: Line 876:
this.num = items.length;
this.num = items.length;
this.items = items.dup;
this.items = items.dup;
foreach (i; 0 .. cast(typeof(indexes[0]))this.num)
this.indexes[i] = i;
this.tot = factorial(this.num);
this.tot = factorial(this.num);
}
}
Line 893: Line 896:
if (tot > 0) {
if (tot > 0) {
size_t j = num - 2;
size_t j = num - 2;

while (items[j] > items[j + 1])
while (indexes[j] > indexes[j + 1])
j--;
j--;
size_t k = num - 1;
size_t k = num - 1;
while (items[j] > items[k])
while (indexes[j] > indexes[k])
k--;
k--;
swap(indexes[k], indexes[j]);
swap(items[k], items[j]);
swap(items[k], items[j]);


Line 903: Line 908:
size_t s = j + 1;
size_t s = j + 1;
while (r > s) {
while (r > s) {
swap(indexes[s], indexes[r]);
swap(items[s], items[r]);
swap(items[s], items[r]);
r--;
r--;
Line 913: Line 919:
Permutations!(doCopy,T) permutations(bool doCopy=true, T)
Permutations!(doCopy,T) permutations(bool doCopy=true, T)
(/*in*/ T[] items)
(/*in*/ T[] items)
pure nothrow {
/*pure*/ nothrow if (isMutable!T) {
return Permutations!(doCopy, T)(items);
return Permutations!(doCopy, T)(items);
} unittest {
} unittest {
Retrieved from "https://rosettacode.org/wiki/Permutations"