Using next_permutation on arrays of ints

Question

Given some arrays, I'd like to loop over every possible permutation of these arrays:

Here's a minimal example:

#include <array>
#include <iostream>
//#include <random>
#include <algorithm>

using namespace std;

int main() {
    // Change the first number of the arrays to get a different number of permutations
    // (this is not wanted)
    array<int, 4> A = { 1,0,0,0 };
    array<int, 4> B = { -9,0,0,0 };
    array<int, 4> C = { 3,0,0,0 };
    array<int, 4> temp[3] = { A, B, C };

    int i = 1;
    do {
        cout << "This is the " << i++ << "-th permutation." << endl;
    } while (next_permutation(temp, temp + 3));
    // (it should yield 3! = 6 permutations but only yields 4)

    return 0;
}

However the number of looped permutations seems to be dependent on the starting value of the array (which is not a feature I wish to use in my project).

This is because next_permutation orders it's elements in lexicographical order.

How can I use this function to get all permutations of the given Arrays? Or do I have to use a different method entirely?

I also know about this answer, but I'd like to avoid sorting my arrays beforehand, since I'm planning to work with a large number of arrays.

Thanks!

You can continue the loop until the initial array content is reached. — 3CEZVQ
– 3CEZVQ, Commented Oct 28, 2024 at 16:41
You could sort temp before you start generating permutations. — Miles Budnek
– Miles Budnek, Commented Oct 28, 2024 at 16:44
You can use 2 loops with prev_permutation() and next_permutation(). — 3CEZVQ
– 3CEZVQ, Commented Oct 28, 2024 at 16:46
next_permutation doesn't (can't) store the "original" somehow the first time you call it. If you want an arbitrary starting point, save a copy yourself and keep going until you have reached the initial state. — molbdnilo
– molbdnilo, Commented Oct 28, 2024 at 16:57
but I'd like to avoid sorting my arrays beforehand, since I'm planning to work with a large number of arrays -- Not tested, but how about calling next_permutation on indices, not the actual values. The indices would start out as 0,1,2,3, i.e. sorted already. This is similar to how you would sort items without actually sorting the items (you sort the indexes). — PaulMcKenzie
– PaulMcKenzie, Commented Oct 28, 2024 at 17:22

lastchance · Accepted Answer · 2024-10-28 17:28:55Z

2

You can do by indirectly mapping the sorted array { 0, 1, 2 }

#include <array>
#include <iostream>
//#include <random>
#include <algorithm>

using namespace std;

int main()
{
    array<int, 4> A = { 1,0,0,0 };
    array<int, 4> B = { -9,0,0,0 };
    array<int, 4> C = { 3,0,0,0 };
    array<int, 4> temp[3] = { A, B, C };
    int ijk[] = { 0, 1, 2 };

    int i = 1;
    do {
        cout << "This is the " << i++ << "-th permutation." << '\n';
        cout << temp[ijk[0]][0] << "  " << temp[ijk[1]][0] << "  " << temp[ijk[2]][0] << '\n';
    } while (next_permutation(ijk, ijk + 3));
}

Output:

This is the 1-th permutation.
1  -9  3
This is the 2-th permutation.
1  3  -9
This is the 3-th permutation.
-9  1  3
This is the 4-th permutation.
-9  3  1
This is the 5-th permutation.
3  1  -9
This is the 6-th permutation.
3  -9  1

answered Oct 28, 2024 at 17:28

lastchance

7,6582 gold badges8 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

PaulMcKenzie Over a year ago

Yes, my comment in the main section describes this. +1

lastchance Over a year ago

Ah, sorry! Actually I'd written the code and was just about to post it when the thread got closed. I hope an uptick on your comment is some remuneration!

haifisch123 Over a year ago

Thank you both. I think this is the most efficient solution.

Marek R Over a year ago

This assumes elements of array are unique. With such assumption it is easy to calculate number of permutations and use this number as a loop counter.

lastchance Over a year ago

It does seem a bit cheaper to permute integer indices than swap whole arrays around.

|

Marek R · Accepted Answer · 2024-10-28 18:26:27Z

Assuming elements are unique (like in the other answer silently assumes) you can just calculate number of iterations:

#include <algorithm>
#include <array>
#include <print>

size_t factorial(size_t x)
{
    size_t r = 1;
    while (x > 1)
        r *= x--;
    return r;
}

int main()
try {
    auto A = std::to_array({ 1, 0, 0, 0 });
    auto B = std::to_array({ -9, 0, 0, 0 });
    auto C = std::to_array({ 3, 0, 0, 0 });
    auto temp = std::to_array({ A, B, C });

    const auto n = factorial(temp.size());
    for (size_t i = 1; i <= n; ++i) {
        std::println("This is the {}-th permuation: {::}", i, temp);
        std::next_permutation(temp.begin(), temp.end());
    }

    return 0;
} catch (const std::exception& e) {
    std::print("Exception: {}\n", e.what());
}

https://godbolt.org/z/oW1Yvsrzh https://godbolt.org/z/MKMMfdf9j

Collectives™ on Stack Overflow

Using next_permutation on arrays of ints

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related