Algoritmos - Combinaciones y permutaciones - algoritmo, rendimiento, permutación, combinaciones

Una pregunta de hwk y aparentemente también una pregunta de entrevista común con la que estoy teniendo problemas:

"Escriba un algoritmo (pseudocódigo) que imprima todos los subconjuntos de tres elementos de un conjunto de n elementos. Los elementos de este conjunto se almacenan en una lista que es la entrada al algoritmo ".

Entonces, por ejemplo, si S = {1,2,3,4} el algoritmo imprimiría estas cuatro combinaciones:

123 124 134 234

¿Alguien puede ofrecer sus pensamientos / una solución?

Respuestas

9 para la respuesta № 1

Recursivamente:

def subset (prefix, list, count):
if count is 0:
print prefix
return
for each element in list:
subset (prefix & element, list beyond element, count - 1)

subset ("", {1,2,3,4}, 3)

Una prueba de concepto de Python:

def subset (prefix, list, count):
if count is 0:
print prefix
return
for i in range (len(list)):
subset ("%s%s"%(prefix,list[i]), list[i+1:], count - 1)

subset ("", "1234", 3)

qué salidas, para varios valores de la cadena de entrada (segundo parámetro a subset)

123456   12345   1234   123   12
------   -----   ----   ---   --
123      123     123    123
124      124     124
125      125     134
126      134     234
134      135
135      145
136      234
145      235
146      245
156      345
234
235
236
245
246
256
345
346
356
456

---

3 para la respuesta № 2

Knuth "s fascile 2 del volumen 4 tiene una solución elegante.

http://cs.utsa.edu/~wagner/knuth/

Edición: es el fascículo 3A. http://cs.utsa.edu/~wagner/knuth/fasc3a.pdf

---

2 para la respuesta № 3

Piensa recursivamente. Quieres subconjuntos de longitud 3. Lo que puedo hacer es que para todos los n en subconjuntos simplemente adjuntaré todos los subconjuntos de longitud 2 a n. Al considerar la longitud 2, no consideraré ningún elemento de 1 a n, ya que estos ya están procesados. S (3, n) = n.S (2, n + 1) para todos los n;

p.ej. cuando n = 1, crearé todos los subconjuntos de longitud 2 con los elementos restantes. (2,3), (3,4), (2,4). Ahora adjuntando 1 obtendré (1,2,3), (1,3,4), (1,2,4). Continuaré esto durante 2. Solo que para 2 al crear los subconjuntos de longitud 2 no consideraré 1. Así que solo tengo un subconjunto de longitud 2 (3,4). Adjuntando esto a 2 recibo (2,3,4) y combinando todo lo que obtengo (1,2,3), (1,3,4), (1,2,4), (2,3,4).

---

1 para la respuesta № 4

Primero traté de resolverlo para el caso específico.cuando S = {1,2,3,4} y n = 3, pero luego decidí hacerlo solo para S = una lista de m elementos y n un número arbitrario> = 1. Además, este es mi primer programa en Java :) así que espero que lo disfruten.

import java.util.Arrays;

public class Combinari {

public static void combinari(int[] array, int n, int[] toPrint){
if(n==1){
for(int i=0;i<array.length;i++){
for(int j=0;j<toPrint.length;j++) System.out.print(toPrint[j]);
System.out.println(array[i]);
}
}
else {
for(int i=0;i<array.length-n+1;i++){
int [] newToPrint = Arrays.copyOf(toPrint, toPrint.length+1);
newToPrint[toPrint.length] = array[i];
int [] new_array =  Arrays.copyOfRange(array, i+1, array.length);
combinari(new_array,n-1,newToPrint);
}
}
}



public static void main(String[] args) {
int [] array = {1,2,3,4,5,6,7};
int [] iaka={}; // iaka est for printing :)
combinari(array, 3, iaka);
System.out.println("");

}

}

---