Início / coding / Perguntas / 79134332
Accepted
haifisch123
Asked: 2024-10-29 00:38:08 +0800 CST

Usando next_permutation em matrizes de ints

  • 772

Dadas algumas matrizes, eu gostaria de fazer um loop em todas as permutações possíveis dessas matrizes:

Aqui está um exemplo mínimo:

#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;
}

Entretanto, o número de permutações em loop parece depender do valor inicial da matriz (o que não é um recurso que desejo usar no meu projeto).

Isso ocorre porque next_permutation ordena seus elementos em ordem lexicográfica.

Como posso usar essa função para obter todas as permutações dos Arrays fornecidos? Ou preciso usar um método totalmente diferente?

Eu também conheço essa resposta , mas gostaria de evitar classificar meus arrays de antemão, pois estou planejando trabalhar com um grande número de arrays.

Obrigado!

c++

2 respostas

  1. Best Answer

    Você pode fazer isso mapeando indiretamente a matriz classificada { 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));
}

    Saída:

    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
    • 2

  2. Supondo que os elementos sejam únicos (como na outra resposta silenciosamente assume), você pode simplesmente calcular o número de iterações:

    #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

    • 0

relate perguntas