Cómo crear una permutación en c ++ usando STL para un número de lugares inferior a la longitud total

15

Tengo un c++ vectorcon std::pair<unsigned long, unsigned long>objetos. Estoy tratando de generar permutaciones de los objetos del vector usando std::next_permutation(). Sin embargo, quiero que las permutaciones sean de un tamaño dado, ya sabes, similar a la permutationsfunción en python donde se especifica el tamaño de la permutación devuelta esperada.

Básicamente, el c++equivalente de

import itertools

list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
    print(permutation)

Demo de Python

(1, 2, 3)                                                                                                                                                                            
(1, 2, 4)                                                                                                                                                                            
(1, 2, 5)                                                                                                                                                                            
(1, 2, 6)                                                                                                                                                                            
(1, 2, 7)                                                                                                                                                                            
(1, 3, 2)
(1, 3, 4)
..
(7, 5, 4)                                                                                                                                                                            
(7, 5, 6)                                                                                                                                                                            
(7, 6, 1)                                                                                                                                                                            
(7, 6, 2)                                                                                                                                                                            
(7, 6, 3)                                                                                                                                                                            
(7, 6, 4)                                                                                                                                                                            
(7, 6, 5) 
d4rk4ng31
fuente
Gracias @ Jarod42 por agregar esa demostración de Python :)
d4rk4ng31
Tuve que hacerlo de mi lado, ya que no sé el resultado de Python, pero estaba bastante seguro de que sé cómo hacerlo en C ++.
Jarod42
Como nota al margen, ¿cómo desea manejar entradas duplicadas como (1, 1)? Python permutaciones proporciona duplicados [(1, 1), (1, 1)], mientras que std::next_permutationevita duplicados (solo {1, 1}).
Jarod42
UH no. No hay duplicados
d4rk4ng31

Respuestas:

6

Puede usar 2 bucles:

  • Toma cada n-tupla
  • iterar sobre permutaciones de esa n-tupla
template <typename F, typename T>
void permutation(F f, std::vector<T> v, std::size_t n)
{
    std::vector<bool> bs(v.size() - n, false);
    bs.resize(v.size(), true);
    std::sort(v.begin(), v.end());

    do {
        std::vector<T> sub;
        for (std::size_t i = 0; i != bs.size(); ++i) {
            if (bs[i]) {
                sub.push_back(v[i]);
            }
        }
        do {
            f(sub);
        }
        while (std::next_permutation(sub.begin(), sub.end()));
    } while (std::next_permutation(bs.begin(), bs.end()));
}

Manifestación

Jarod42
fuente
¿Cuál será la complejidad temporal de este código? ¿Será O (places_required * n) para el caso promedio y O (n ^ 2) para el peor de los casos? También estoy adivinando O (n) para el mejor caso, es decir, un lugar
d4rk4ng31
2
@ d4rk4ng31: De hecho, encontramos cada permutación solo una vez. la complejidad de std::next_permutation"no está clara", ya que cuenta el intercambio (lineal). La extracción del sub vector puede mejorarse, pero no creo que cambie la complejidad. Además, el número de permutación depende del tamaño del vector, por lo que los 2 parámetros no son independientes.
Jarod42
¿No debería ser eso std::vector<T>& v?
LF
@LF: es a propósito. Considero que no tengo que cambiar el valor de la persona que llama (estoy ordenando vactualmente). Podría pasar por referencia constante y crear una copia ordenada en el cuerpo en su lugar.
Jarod42
@ Jarod42 Oh, lo siento, leí completamente el código. Sí, pasar por valor es lo correcto para hacer aquí.
LF
4

Si la eficiencia no es la principal preocupación, podemos iterar sobre todas las permutaciones y omitir aquellas que difieren en un sufijo seleccionando solo cada (N - k)!una de ellas. Por ejemplo, para N = 4, k = 2, tenemos permutaciones:

12 34 <
12 43
13 24 <
13 42
14 23 <
14 32
21 34 <
21 43
23 14 <
23 41
24 13 <
24 31
...

donde inserté un espacio para mayor claridad y (N-k)! = 2! = 2marqué cada permutación con <.

std::size_t fact(std::size_t n) {
    std::size_t f = 1;
    while (n > 0)
        f *= n--;
    return f;
}

template<class It, class Fn>
void generate_permutations(It first, It last, std::size_t k, Fn fn) {
    assert(std::is_sorted(first, last));

    const std::size_t size = static_cast<std::size_t>(last - first);
    assert(k <= size);

    const std::size_t m = fact(size - k);
    std::size_t i = 0;
    do {
        if (i++ == 0)
            fn(first, first + k);
        i %= m;
    }
    while (std::next_permutation(first, last));
}

int main() {
    std::vector<int> vec{1, 2, 3, 4};
    generate_permutations(vec.begin(), vec.end(), 2, [](auto first, auto last) {
        for (; first != last; ++first)
            std::cout << *first;
        std::cout << ' ';
    });
}

Salida:

12 13 14 21 23 24 31 32 34 41 42 43
Evg
fuente
3

Aquí hay un algoritmo eficiente que no usa std::next_permutationdirectamente, pero hace uso de los caballos de trabajo de esa función. Es decir, std::swapy std::reverse. Como ventaja, está en orden lexicográfico .

#include <iostream>
#include <vector>
#include <algorithm>

void nextPartialPerm(std::vector<int> &z, int n1, int m1) {

    int p1 = m1 + 1;

    while (p1 <= n1 && z[m1] >= z[p1])
        ++p1;

    if (p1 <= n1) {
        std::swap(z[p1], z[m1]);
    } else {
        std::reverse(z.begin() + m1 + 1, z.end());
        p1 = m1;

        while (z[p1 + 1] <= z[p1])
            --p1;

        int p2 = n1;

        while (z[p2] <= z[p1])
            --p2;

        std::swap(z[p1], z[p2]);
        std::reverse(z.begin() + p1 + 1, z.end());
    }
}

Y llamándolo tenemos:

int main() {
    std::vector<int> z = {1, 2, 3, 4, 5, 6, 7};
    int m = 3;
    int n = z.size();

    const int nMinusK = n - m;
    int numPerms = 1;

    for (int i = n; i > nMinusK; --i)
        numPerms *= i;

    --numPerms;

    for (int i = 0; i < numPerms; ++i) {
        for (int j = 0; j < m; ++j)
            std::cout << z[j] << ' ';

        std::cout << std::endl;
        nextPartialPerm(z, n - 1, m - 1);
    }

    // Print last permutation
    for (int j = 0; j < m; ++j)
            std::cout << z[j] << ' ';

    std::cout << std::endl;

    return 0;
}

Aquí está la salida:

1 2 3 
1 2 4 
1 2 5 
1 2 6 
1 2 7
.
.
.
7 5 6 
7 6 1 
7 6 2 
7 6 3 
7 6 4 
7 6 5

Aquí hay un código ejecutable de ideone

Joseph Wood
fuente
2
Incluso podría imitar aún más con la firmabool nextPartialPermutation(It begin, It mid, It end)
Jarod42
2
Demostración .
Jarod42
@ Jarod42, esa es una muy buena solución. Debería agregarlo como respuesta ...
Joseph Wood
Mi idea inicial era mejorar tu respuesta, pero está bien, agregó.
Jarod42
3

Al girar la respuesta de Joseph Wood con la interfaz de iterador, es posible que tenga un método similar a std::next_permutation:

template <typename IT>
bool next_partial_permutation(IT beg, IT mid, IT end) {
    if (beg == mid) { return false; }
    if (mid == end) { return std::next_permutation(beg, end); }

    auto p1 = mid;

    while (p1 != end && !(*(mid - 1) < *p1))
        ++p1;

    if (p1 != end) {
        std::swap(*p1, *(mid - 1));
        return true;
    } else {
        std::reverse(mid, end);
        auto p3 = std::make_reverse_iterator(mid);

        while (p3 != std::make_reverse_iterator(beg) && !(*p3 < *(p3 - 1)))
            ++p3;

        if (p3 == std::make_reverse_iterator(beg)) {
            std::reverse(beg, end);
            return false;
        }

        auto p2 = end - 1;

        while (!(*p3 < *p2))
            --p2;

        std::swap(*p3, *p2);
        std::reverse(p3.base(), end);
        return true;
    }
}

Manifestación

Jarod42
fuente
1

Esta es mi solución después de pensarlo

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> job_list;
    std::set<std::vector<int>> permutations;
    for (unsigned long i = 0; i < 7; i++) {
        int job;
        std::cin >> job;
        job_list.push_back(job);
    }
    std::sort(job_list.begin(), job_list.end());
    std::vector<int> original_permutation = job_list;
    do {
        std::next_permutation(job_list.begin(), job_list.end());
        permutations.insert(std::vector<int>(job_list.begin(), job_list.begin() + 3));
    } while (job_list != original_permutation);

    for (auto& permutation : permutations) {
        for (auto& pair : permutation) {
            std::cout << pair << " ";
        }
        std::endl(std::cout);
    }

    return 0;
}

Por favor comente sus pensamientos

d4rk4ng31
fuente
2
No es equivalente al mío, es más equivalente a la respuesta de Evg (pero Evg omite los duplicados de manera más eficiente). permutede hecho solo podría set.insert(vec);eliminar un factor importante.
Jarod42
¿Cuál es la complejidad del tiempo ahora?
d4rk4ng31
1
Yo diría O(nb_total_perm * log(nb_res))( nb_total_permque es sobre todo factorial(job_list.size())y nb_restamaño del resultado: permutations.size()), Así que sigue siendo demasiado grande. (pero ahora manejas entradas duplicadas contrarias a Evg)
Jarod42