Search
Array permutations
Sep 11
Vino
Sep 11
jfondren
Sep 11
jfondren
Sep 11
Vino
Sep 11
Vino
Sep 11
Dukc
Sep 16
Elmar
Sep 16
Elmar

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

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

``````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);
}
``````

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]"

``````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.

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

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

This `drop` isn't necessary.

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

``````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

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

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?

``````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.)

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.