www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array permutations

reply Vino <akashvino79 gmail.com> writes:
Hi All,

    Request your help on the below to print the below array as 
"Required output", Was able to get these values 
"[1,2],[2,3],[3,4],[4,5]" by using list.slide(2), need your help 
to get values "1,3],[1,4],[1,5],[2,4],[2,5],[3,5]"

auto list[] = [1,2,3,4,5]

Required output
[1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]

From,
Vino
Sep 11 2021
next sibling parent reply jfondren <julian.fondren gmail.com> writes:
On Saturday, 11 September 2021 at 19:37:42 UTC, Vino wrote:

 Hi All,

    Request your help on the below to print the below array as 
 "Required output", Was able to get these values 
 "[1,2],[2,3],[3,4],[4,5]" by using list.slide(2), need your 
 help to get values "1,3],[1,4],[1,5],[2,4],[2,5],[3,5]"

 auto list[] = [1,2,3,4,5]

 Required output
 [1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]

 From,
 Vino


I don't see the pattern just from the required output. If you 
have an English description of what you want, it might be easier.

Anyway, take a look at

```d
unittest {
     import std.algorithm : cartesianProduct, filter, map, sort;
     import std.range : drop;
     import std.array : array;

     auto list = [1,2,3,4,5];
     auto required = 
[[1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]];
     auto pairs = list.cartesianProduct(list.drop(1))
         .filter!"a[0] < a[1]"
         .map!array
         .array;
     assert(pairs == [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 
4], [2, 5], [3, 4], [3, 5], [4, 5]]);
     assert(required.sort.array == pairs);
}
```
Sep 11 2021
next sibling parent jfondren <julian.fondren gmail.com> writes:
On Saturday, 11 September 2021 at 19:57:26 UTC, jfondren wrote:

     auto pairs = list.cartesianProduct(list.drop(1))


This `drop` isn't necessary.
Sep 11 2021
prev sibling parent reply Vino <akashvino79 gmail.com> writes:
On Saturday, 11 September 2021 at 19:57:26 UTC, jfondren wrote:

 On Saturday, 11 September 2021 at 19:37:42 UTC, Vino wrote:

 Hi All,

    Request your help on the below to print the below array as 
 "Required output", Was able to get these values 
 "[1,2],[2,3],[3,4],[4,5]" by using list.slide(2), need your 
 help to get values "1,3],[1,4],[1,5],[2,4],[2,5],[3,5]"

 auto list[] = [1,2,3,4,5]

 Required output
 [1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]

 From,
 Vino


 I don't see the pattern just from the required output. If you 
 have an English description of what you want, it might be 
 easier.

 Anyway, take a look at

 ```d
 unittest {
     import std.algorithm : cartesianProduct, filter, map, sort;
     import std.range : drop;
     import std.array : array;

     auto list = [1,2,3,4,5];
     auto required = 
 [[1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]];
     auto pairs = list.cartesianProduct(list.drop(1))
         .filter!"a[0] < a[1]"
         .map!array
         .array;
     assert(pairs == [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], 
 [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]);
     assert(required.sort.array == pairs);
 }
 ```


Hi,

    Thank you very much, let me try to explain the actual 
requirement, the actual requirement is to find all the 
permutations of a given array, I modified your code and it gives 
me the exact output , but i need help to remove the array which 
has the same value as below

Example:
void main() {
import std.algorithm : cartesianProduct, filter, map, sort;
import std.range : drop;
import std.array : array;
import std.stdio : writeln;

     auto list = [1,2,3,4,5];
     auto pairs = list.cartesianProduct(list)
         .map!array
         .array;
      writeln(pairs);
}

Output
[
[1, 1], /* shodule not print this array */
[1, 2],
[1, 3],
[1, 4],
[1, 5],
[2, 1],
[2, 2], /* should not print this array */
[2, 3],
[2, 4],
[2, 5],
[3, 1],
[3, 2],
[3, 3], /* should not print this array */
[3, 4],
[3, 5],
[4, 1],
[4, 2],
[4, 3],
[4, 4], /* should not print this array */
[4, 5],
[5, 1],
[5, 2],
[5, 3],
[5, 4],
[5, 5] /* should not print this array */
]

From,
Vino
Sep 11 2021
parent Vino <akashvino79 gmail.com> writes:
On Saturday, 11 September 2021 at 23:04:29 UTC, Vino wrote:

 On Saturday, 11 September 2021 at 19:57:26 UTC, jfondren wrote:

 [...]


 Hi,

    Thank you very much, let me try to explain the actual 
 requirement, the actual requirement is to find all the 
 permutations of a given array, I modified your code and it 
 gives me the exact output , but i need help to remove the array 
 which has the same value as below

 [...]


Hi,

   Was able to resolve the issue by adding the filter 
".filter!"a[0] != a[1]"

From,
Vino
Sep 11 2021
prev sibling next sibling parent Dukc <ajieskola gmail.com> writes:
On Saturday, 11 September 2021 at 19:37:42 UTC, Vino wrote:

    Request your help on the below to print the below array as 
 "Required output", Was able to get these values 
 "[1,2],[2,3],[3,4],[4,5]" by using list.slide(2), need your 
 help to get values "1,3],[1,4],[1,5],[2,4],[2,5],[3,5]"


```d
import std;
auto slideEnds(List)(List list, size_t slideLen)
{	return list.slide(slideLen).map!(window => [window.front, 
window.back]);
}
void main()
{	auto list = [1,2,3,4,5];

     iota(2, list.length)
     .map!(slideLen => list.slideEnds(slideLen))
     .joiner
     .writeln;
}
```

This almost does the trick. It leaves out `[1, 5]` for some 
reason I didn't bother to check though.
Sep 11 2021
prev sibling parent reply Elmar <chrehme gmx.de> writes:
On Saturday, 11 September 2021 at 19:37:42 UTC, Vino wrote:

 Hi All,

    Request your help on the below to print the below array as 
 "Required output", Was able to get these values 
 "[1,2],[2,3],[3,4],[4,5]" by using list.slide(2), need your 
 help to get values "1,3],[1,4],[1,5],[2,4],[2,5],[3,5]"

 auto list[] = [1,2,3,4,5]

 Required output
 [1,2],[2,3],[3,4],[4,5],[1,3],[1,4],[1,5],[2,4],[2,5],[3,5]

 From,
 Vino


Would this be a valid solution to your problem?

```D
pure  safe nothrow
T[][] computeChoices(T)(T[] values, size_t tupleSize = 2)
{
     if (tupleSize == 0) {
      	return [[]];
     }

     T[][] choices = [];
     tupleSize--;
     foreach(i, element; values[0 .. $ - tupleSize])
     {
         import std.algorithm.iteration : map;
         import std.array : array;
         choices ~= computeChoices(values[i+1 .. $], tupleSize)
             		.map!(choice => element ~ choice)
             		.array;
     }

     return choices;
}

unittest
{
     assert(computeChoices([1, 2, 3, 4, 5], 2)
            	== [[1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], 
[3,4], [3,5], [4,5]] );
}
```

You can choose in the 2nd parameter how large the inner arrays 
should be. It uses GC to allocate the result via the function 
`array`. If that is a problem, you could choose an allocator from 
`std.experimental.allocator` and use the `makeArray` function 
with the allocator instead of the `array` function. (Manual 
deallocation could be required then as well.)
Sep 16 2021
parent Elmar <chrehme gmx.de> writes:
I also should discourage its current form with large 
`tupleSize`s. The computation is in O(exp(values.length)). 
Instead of `~=` I would suggest an `std.array.appender` of arrays 
instead of an 2D-array for the `choices`, if the `choices` become 
large. Most efficient is a preallocated array capacity. In that 
case `~=` has very low overhead.
Sep 16 2021