c++ - permutar - permutaciones sin repeticion pseint

Cómo obtener la permutación del índice después de la clasificación

Question

Dada una matriz arr = {5, 16, 4, 7} , podemos clasificarla por sort(arr, arr+sizeof(arr)/sizeof(arr[0])) . así que ahora la matriz arr = {4, 5, 7, 16} y el índice de permutación para la matriz ordenada es {2, 0, 3, 1} . En otras palabras, el arr[2] en la matriz original es ahora el elemento más pequeño en la matriz ordenada en la posición 0 .

¿Hay alguna forma eficiente para que podamos obtener el índice de permutación?

Gracias

Answer 1

¿Por qué no poner algunos datos de satélite? En lugar de ordenar los números, simplemente ordena los pares de números y sus índices. Dado que la clasificación se realiza primero en el primer elemento del par, esto no debe interrumpir un algoritmo de clasificación estable.

Para algoritmos inestables, esto lo cambiará a uno estable.

Pero tenga en cuenta que si intenta ordenar de esta manera, se genera el índice al ordenar, no después.

Además, dado que conocer el índice de permutación llevaría a un algoritmo de clasificación O (n), no puede hacerlo más rápido que O (nlogn).

Answer 2

Bueno, en c ++ podemos usar el tipo de datos de par para hacer esto fácilmente. Código de muestra a continuación;

arr = {5, 16, 4, 7};
vector<pair<int,int> >V;
for(int i=0;i<4;i++){
pair<int,int>P=make_pair(arr[i],i);
V.push_back(P);
}
sort(V.begin(),V.end());

Así que V [i] .first es el valor i y V [i] .second es el índice i. Así que para imprimir el índice en la matriz ordenada.

for(int i=0;i<4;i++)cout<<V[i].second<<endl;

Tenga en cuenta que al ordenar una matriz (o vector) de elementos de par, la matriz se ordena primero en función de los primeros valores. Si dos pares tienen el mismo primer valor, se ordenan según su segundo valor.

Answer 3

Cree una matriz de índices, rellénela con los números 0..N-1 y clasifíquela utilizando un comparador personalizado. El comparador debe comparar los elementos de la matriz original en los índices lhs y rhs . La clasificación de la matriz de índices de esta manera los reordena como una permutación:

vector<int> data = {5, 16, 4, 7};
vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
index[i] = i;
}
sort(index.begin(), index.end(),
[&](const int& a, const int& b) {
return (data[a] < data[b]);
}
);
for (int i = 0 ; i != index.size() ; i++) {
cout << index[i] << endl;
}

Esto imprime 2, 0, 3, 1

Aquí hay una demostración de ideone .

Nota: puede usar el index para recuperar los data en orden ordenado:

for (int i = 0 ; i != index.size() ; i++) {
cout << data[index[i]] << endl;
}

Answer 4

Creo que podemos resolver este problema sin usar vector. Soy novato, para ser honesto, no entiendo lo que escribiste anteriormente, y todos ustedes usaron el vector que estudiaré más adelante :))) (Soy perezoso) Este es mi camino:

// Primero, copia la matriz a [] a la matriz b []

 void copyarray(double b[],double a[],int n){
for(int i=0;i<n;i++)b[i]=a[i];
}

// Segundo, ordena la matriz a [] (disminuir)

/ * Tercero, el "ordenador" array a [], que significa: en el array a [], si existen los mismos valores, ¡se fusionarán en uno! estableceré la matriz o [] es "la matriz ordenada a []" * /

 void sorter(double o[],double a[],int n,int &dem){
int i;
o[0]=a[0];
for(i=1;i<n;i++){
if(a[i]!=a[i-1]){
dem++; o[dem]=a[i];
}
}
dem++;
}

/ * Cuarto, nuestro principal objetivo: obtener el índice: pondré el índice en la matriz c [] * /

void index_sort(double o[],double b[], double c[], int dem, int n){
int i,j,chiso=0;
for(j=0;j<dem;j++){
for(i=0;i<n;i++){
if(b[i]==o[j]){
c[chiso]=i;
chiso++;
}
}
}
}
// DONE!
int main(){
int n,dem=0;
double a[100],b[100],c[100],o[100];
cin>>n;
input(a,n);
copyarray(b,a,n);
copyarray(c,a,n);
sort(a,n);
sorter(o,a,n,dem);
index_sort(o,b,c,dem,n);
for(int i=0;i<n;i++) cout<<c[i]<<" ";
}

Answer 5

Hace poco tuve que resolver un problema similar en PHP. Usted crea una función de comparación local para ser utilizada por el algoritmo de clasificación UASORT de PHP. Llame a array_keys () en la matriz ordenada, y eso debería escupir su matriz de permutación.

// matriz de prueba

$ tArray = array (''2'', ''10'', ''1'', ''23'', ''8'', ''3'');

// ordenar la matriz; para mantener la asociación de índices, use uasort; mas usa usort, etc

uasort ($ tArray, ''compareSize'');

// las claves resultantes son sus índices de permutación (si se usa uasort en el paso anterior)

$ Keys = array_keys ($ tArray);

// función de comparación local

función compareSize ($ a, $ b) {

if ($ a == $ b) {return 0; } else {return ($ a <$ b)? -1: 1; }

}

================================================== ===================== Resultados:

ordenado =: Array ([2] => 1 [0] => 2 [5] => 3 [4] => 8 [1] => 10 [3] => 23)

teclas =: Array ([0] => 2 [1] => 0 [2] => 5 [3] => 4 [4] => 1 [5] => 3)

Answer 6

Multimap puede venir al rescate.

template<typename TIn, typename TOut>
sortindex(const TIn &first, const TIn &last, TOut &out) {
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
for(auto &&p: sindex)
*out++ = p.second;
}

que se puede utilizar de esta manera:

std::vector<size_t> a{32, 22, 45, 9, 12, 15};
std::vector<size_t> indexes;
sortindex(a.begin(), a.end(), std::back_inserter(indexes));

Si se necesitaría un acoplamiento entre los valores ordenados y el índice, entonces el multimapa se puede devolver directamente, en lugar de escribir los índices en el iterador de salida.

template<typename TIn>
auto
sortindex(const TIn &first, const TIn &last)
--> std::multimap<typename std::decay<decltype(*first)>::type, size_t>
{ // return value can be commented out in C++14
using ValT = typename std::decay<decltype(*first)>::type;
std::multimap<ValT, size_t> sindex;
for(auto p=first; p != last; p++)
sindex.emplace(*p, std::distance(first, p));
return sindex;
}

Answer 7

Sí, hay uno con el tiempo O(NlogN) Dado que la clasificación lleva el tiempo O(NlogN) todos modos, esto no afectará la complejidad del tiempo en general.
Complejidad de tiempo : O(NlogN)
Complejidad del espacio : O(N)
donde N = número de elementos en la matriz de entrada

Algoritmo:

1. Hacer copia de la matriz de entrada (P) llamarlo Q.
2. Ordenar la matriz de entrada P.
3. Para cada número en Q, haga una búsqueda binaria para encontrar el índice de ese elemento en P.