www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Permutations of array (slice) ?

reply Kevin Bailey <keraba yahoo.com> writes:
Could I get some help with a trivial question, I'm sure? How do 
pass a slice as a range? This code:

import std.algorithm; // permutations
import std.range; // replicate
import std.stdio; // writeln

int main()
{
     char[] as = replicate(['a'], 5);
     as[0] = 'b';
     foreach (perm; as.permutations)
         writeln(perm);
}

appears to complain (actual error below) that 'as' is not a range.

Using the slice trick "as[]" from:

https://forum.dlang.org/thread/oxohqaicmpteesugsdnk forum.dlang.org

doesn't help either. Something obvious I'm missing, I hope.

perm.d:8:26: error: none of the overloads of template 
‘std.algorithm.iteration.permutations’ are callable using 
argument types ‘!()(char[])’
     8 |         foreach (perm; as.permutations)
       |                          ^
/usr/lib/gcc/x86_64-linux-gnu/13/include/d/std/algorithm/iteration.d:7919:20:
note: Candidate is: ‘permutations(Range)(Range r)’
      with `Range = char[]`
   must satisfy the following constraint:
`       isRandomAccessRange!Range`
  7919 | Permutations!Range permutations(Range)(Range r)
       |                    ^
Dec 12 2023
parent reply Paul Backus <snarwin gmail.com> writes:
On Tuesday, 12 December 2023 at 14:57:48 UTC, Kevin Bailey wrote:

 perm.d:8:26: error: none of the overloads of template 
 ‘std.algorithm.iteration.permutations’ are callable using 
 argument types ‘!()(char[])’
     8 |         foreach (perm; as.permutations)
       |                          ^
 /usr/lib/gcc/x86_64-linux-gnu/13/include/d/std/algorithm/iteration.d:7919:20:
note: Candidate is: ‘permutations(Range)(Range r)’
      with `Range = char[]`
   must satisfy the following constraint:
 `       isRandomAccessRange!Range`
  7919 | Permutations!Range permutations(Range)(Range r)
       |                    ^


Because of autodecoding [1], slices of char and wchar are treated 
by Phobos as bidirectional ranges of dchar. (They are not 
random-access ranges because UTF-8 and UTF-16 are variable-length 
encodings.)

To work around this, use std.utf.byChar:

     import std.utf: byChar;
     foreach (perm; as.byChar.permutations)
         writeln(perm);

[1] 
http://ddili.org/ders/d.en/ranges.html#ix_ranges.decoding,%20automatic
Dec 12 2023
parent reply Kevin Bailey <keraba yahoo.com> writes:
On Tuesday, 12 December 2023 at 15:20:23 UTC, Paul Backus wrote:

 Because of autodecoding [1], slices of char and wchar are 
 treated by Phobos as bidirectional ranges of dchar. (They are 
 not random-access ranges because UTF-8 and UTF-16 are 
 variable-length encodings.)

 To work around this, use std.utf.byChar:

     import std.utf: byChar;
     foreach (perm; as.byChar.permutations)
         writeln(perm);

 [1] 
 http://ddili.org/ders/d.en/ranges.html#ix_ranges.decoding,%20automatic


ah, many thanks, I never would have figured that out.

But unfortunately, the code shown now prints 120 lines of:

baaaa

120 being suspiciously equal to 5!. The documentation[2] seems to 
imply that this should be:

baaaa
abaaa
...

When I replace the char[] with int[] [2, 1, 1, 1, 1], it produces 
120 lines of random arrangements of the input, but mostly just 
repeating the input.

Clearly it's doing permutations of a separate array of [0, 1, 2, 
3, 4], and then replacing each index with the element at that 
index (or the equivalent) but it's not even doing that right.

I'll play with nextPermutation. I suspect it would have to be 
implemented the way that I'm expecting.

[2] 
https://dlang.org/library/std/algorithm/iteration/permutations.html
Dec 12 2023
parent reply Nick Treleaven <nick geany.org> writes:
On Tuesday, 12 December 2023 at 16:21:46 UTC, Kevin Bailey wrote:

 On Tuesday, 12 December 2023 at 15:20:23 UTC, Paul Backus wrote:
 But unfortunately, the code shown now prints 120 lines of:

 baaaa

 120 being suspiciously equal to 5!. The documentation[2] seems 
 to imply that this should be:

 baaaa
 abaaa
 ...


This code works for me. (The last 20+ lines are `aaaab`):
```d
import std;
void main() {
     char[] as = replicate(['a'], 5);
     as[0] = 'b';
     foreach (perm; as.byChar.permutations)
         writeln(perm);
}
```
Try it on https://run.dlang.io/. Maybe there's some issue on your 
machine?
Also if you use `string as = "abcde";` you can see the 
permutations better.
Dec 13 2023
parent Kevin Bailey <keraba yahoo.com> writes:
On Wednesday, 13 December 2023 at 20:28:11 UTC, Nick Treleaven 
wrote:

 This code works for me. (The last 20+ lines are `aaaab`):
 ```d
 import std;
 void main() {
     char[] as = replicate(['a'], 5);
     as[0] = 'b';
     foreach (perm; as.byChar.permutations)
         writeln(perm);
 }
 ```
 Try it on https://run.dlang.io/. Maybe there's some issue on 
 your machine?
 Also if you use `string as = "abcde";` you can see the 
 permutations better.


Revisiting this, I see that it works now. I suspect that I had

     writeln(as);

Nevertheless, nextPermutation() does what I really want, which is:

(given as[4] = 'b')

aaaab
aaaba
aabaa
abaaa
baaaa
Dec 15 2023