con - Programa para imprimir permutaciones de elementos dados

permutaciones y combinaciones

Question

Recientemente participé en la competencia de programación certificada de ACM. Esta es la pregunta que no podía hacer en ese momento:

"Dado un conjunto de enteros que tienen n elementos, escriba un programa para imprimir todas las permutaciones".

Por favor dime cómo hacer esta pregunta. ¿Hay algún algoritmo para hacer este tipo de preguntas?

Answer 1

Aquí hay una solución iterativa:

Primero ordena la matriz.

• Encuentre el índice máximo ia [i + 1]. (si no existe tal índice, no quedan más permutaciones)

Encuentra el índice máximo j

Cambia a [i] y a [j].

Invierta a [i + 1] .. a [n-1] y vaya al paso *.

Answer 2

Un enfoque recursivo debería funcionar bien:

If the list is empty
    Return the only possible permutation, an empty list.

Else
    For each element of the list
        Put the element at the first place (i.e. swap it with the first element)
          (If the element is same as the first one, don''t swap)
        Recursively find all the permutations of the rest of the list

Este algoritmo no generará permutaciones repetidas.

Aquí hay una implementación de Python:

def permute(s):
    if len(s) == 0:
        return [[]]

    ret = [s[0:1] + x for x in permute(s[1:])]

    for i in range(1, len(s)):
        if s[i] == s[0]:
            continue
        s[0], s[i] = s[i], s[0]
        ret += [s[0:1] + x for x in permute(s[1:])]

    return ret

s = [0, 1, 2, 3]
for x in permute(s):
    print x

Lo similar en C debería ser así:

void swap(char* str, int i, int j)
{
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

void permute(char *string, int start, int end)
{
    if(start == end)
    {
        printf("%s/n", string);
        return;
    }

    permute(string, start + 1, end);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(string[start] == string[i])
            continue;
        swap(string, start, i);
        permute(string, start + 1, end);
        swap(string, start, i);
    }
}

Answer 3

suponiendo que no haya repeticiones: simplemente cambie cada elemento con todos los elementos siguientes posibles e invoque recursivamente la función.

void permute(int *array,int i,int length) { 
  if (length == i){
     printArray(array,length);
     return;
  }
  int j = i;
  for (j = i; j < length; j++) { 
     swap(array+i,array+j);
     permute(array,i+1,length);
     swap(array+i,array+j);
  }
  return;
}

Puede ver el código con funciones auxiliares swap() e printArray() realizando con un caso de prueba básico en ideone

Bonificación : Esto es similar a la idea de la mezcla de fisher-yates , pero aquí -intenta cambiar el elemento en i con el siguiente elemento elegido al azar- lo cambias con todos ellos, cada uno a la vez.

Answer 4

Para obtener la permutación que tienes que usar recussion y backtracking, puedes resolverla también a través de la fuerza bruta, pero se vuelve compleja

    void swap(int *x1,int *x2)
    {
        int x=*x1;
        *x1=*x2;
        *x2=x;
    }
    void per(int *arr,int st,int ls)
    {
        int i=0;
        if(st==ls)
        {
            int k;
            for(k=0;k<ls;k++)
            {
                printf("%d ",arr[k]);
            }
        printf("/n");
    }
        else
        {
            for(i=st;i<ls;i++)
            {
                swap(arr+st,arr+i);
                per(arr,st+1,ls);
                swap(arr+st,arr+i);
            }
        }
}

int main()
{
    int arr[4]={1,2,3,1};
    int st=0;
    int ls=4;
    per(arr,st,ls);
}