Encuentre todos los subconjuntos de longitud k en una matriz

Dado un conjunto {1,2,3,4,5...n} de n elementos, necesitamos encontrar todos los subconjuntos de longitud k.

Por ejemplo, si n = 4 yk = 2, la output sería {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} .

Ni siquiera puedo descifrar cómo comenzar. No tenemos que usar las funciones de la biblioteca incorporada como next_permutation, etc.

Necesita el algoritmo y la implementación en C / C ++ o Java.

Recursion es tu amigo para esta tarea.

Para cada elemento: “adivinar” si está en el subconjunto actual e invocar recursivamente con la conjetura y un superconjunto más pequeño que puede seleccionar. Si lo hace para las conjeturas “sí” y “no”, se obtendrán todos los subconjuntos posibles.
Restringirse a una determinada longitud se puede hacer fácilmente en una cláusula de detención.

Código Java:

 private static void getSubsets(List superSet, int k, int idx, Set current,List> solution) { //successful stop clause if (current.size() == k) { solution.add(new HashSet<>(current)); return; } //unseccessful stop clause if (idx == superSet.size()) return; Integer x = superSet.get(idx); current.add(x); //"guess" x is in the subset getSubsets(superSet, k, idx+1, current, solution); current.remove(x); //"guess" x is not in the subset getSubsets(superSet, k, idx+1, current, solution); } public static List> getSubsets(List superSet, int k) { List> res = new ArrayList<>(); getSubsets(superSet, k, 0, new HashSet(), res); return res; } 

Invocar con:

 List superSet = new ArrayList<>(); superSet.add(1); superSet.add(2); superSet.add(3); superSet.add(4); System.out.println(getSubsets(superSet,2)); 

Rendirá:

 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 

Utilice una representación de vector de bits del conjunto y utilice un algoritmo similar al que hace std :: next_permutation en 0000.1111 (nk zeroes, k ones). Cada permutación corresponde a un subconjunto de tamaño k.

Mira mi solución

 import java.util.ArrayList; import java.util.HashSet; import java.util.Set; public class Subset_K { public static void main(String[]args) { Set x; int n=4; int k=2; int arr[]={1,2,3,4}; StringBuilder sb=new StringBuilder(); for(int i=1;i<=(nk);i++) sb.append("0"); for(int i=1;i<=k;i++) sb.append("1"); String bin=sb.toString(); x=generatePerm(bin); Set> outer=new HashSet>(); for(String s:x){ int dec=Integer.parseInt(s,2); ArrayList inner=new ArrayList(); for(int j=0;j0) inner.add(arr[j]); } outer.add(inner); } for(ArrayList z:outer){ System.out.println(z); } } public static Set generatePerm(String input) { Set set = new HashSet(); if (input == "") return set; Character a = input.charAt(0); if (input.length() > 1) { input = input.substring(1); Set permSet = generatePerm(input); for (String x : permSet) { for (int i = 0; i <= x.length(); i++) { set.add(x.substring(0, i) + a + x.substring(i)); } } } else { set.add(a + ""); } return set; } } 

Estoy trabajando en un conjunto de 4 elementos para fines de prueba y usando k = 2. Lo que trato de hacer es generar inicialmente una cadena binaria donde se establecen k bits y no se establecen nk bits. Ahora usando esta cadena, encuentro todas las permutaciones posibles de esta cadena. Y luego, usando estas permutaciones, saco el elemento respectivo en el conjunto. Sería genial si alguien pudiera hablarme sobre la complejidad de este problema.

Esto es python. Perdón por el español;)

 from pprint import pprint conjunto = [1,2,3,4, 5,6,7,8,9,10] k = 3 lista = [] iteraciones = [0] def subconjuntos(l, k): if k == len(l): if not l in lista: lista.append(l) return for i in l: aux = l[:] aux.remove(i) result = subconjuntos(aux, k) iteraciones[0] += 1 if not result in lista and result: lista.append( result) subconjuntos(conjunto, k) print (lista) print ('cant iteraciones: ' + str(iteraciones[0])) 
  #include #include #include using namespace std; vector v; vector > result; void subset(int arr[],int k,int n,int idx){ if(idx==n) return; if(k==1){ for(int i=idx;i 

Por favor revisa mi solución:

 private static void printPermutations(List list, int subSetSize) { List prefixList = new ArrayList(); printPermutations(prefixList, list, subSetSize); } private static void printPermutations(List prefixList, List list, int subSetSize) { if (prefixList.size() == subSetSize) { System.out.println(prefixList); } else { for (int i = 0; i < list.size(); i++) { Integer removed = list.remove(i); prefixList.add(removed); printPermutations(prefixList, list, subSetSize); prefixList.remove(removed); list.add(i, removed); } } } 

Esto es similar a las permutaciones de cadenas:

 private static void printPermutations(String str) { printAllPermutations("", str); } private static void printAllPermutations(String prefix, String restOfTheString) { int len = restOfTheString.length(); System.out.println(prefix); for (int i = 0; i < len; i++) { printAllPermutations(prefix + restOfTheString.charAt(i), restOfTheString.substring(0, i) + restOfTheString.substring(i + 1, len)); } } 

Esta es una implementación en F #:

 // allSubsets: int -> int -> Set> let rec allSubsets nk = match n, k with | _, 0 -> Set.empty.Add(Set.empty) | 0, _ -> Set.empty | n, k -> Set.union (Set.map (fun s -> Set.add ns) (allSubsets (n-1) (k-1))) (allSubsets (n-1) k) 

Puedes probarlo en el F # REPL:

 > allSubsets 3 2;; val it : Set> = set [set [1; 2]; set [1; 3]; set [2; 3]] > allSubsets 4 2;; val it : Set> = set [set [1; 2]; set [1; 3]; set [1; 4]; set [2; 3]; set [2; 4]; set [3; 4]] 

Esta clase de Java implementa el mismo algoritmo:

 import java.util.HashSet; import java.util.Set; public class AllSubsets { public static Set> allSubsets(int setSize, int subsetSize) { if (subsetSize == 0) { HashSet> result = new HashSet<>(); result.add(new HashSet<>()); return result; } if (setSize == 0) { return new HashSet<>(); } Set> sets1 = allSubsets((setSize - 1), (subsetSize - 1)); for (Set set : sets1) { set.add(setSize); } Set> sets2 = allSubsets((setSize - 1), subsetSize); sets1.addAll(sets2); return sets1; } } 

Si no te gusta F # o Java, visita este sitio web. Enumera soluciones a su problema particular en varios lenguajes de progtwigción:

http://rosettacode.org/wiki/Combinations

Implementación de JavaScript:

 var subsetArray = (function() { return { getResult: getResult } function getResult(array, n) { function isBigEnough(value) { return value.length === n; } var ps = [ [] ]; for (var i = 0; i < array.length; i++) { for (var j = 0, len = ps.length; j < len; j++) { ps.push(ps[j].concat(array[i])); } } return ps.filter(isBigEnough); } })(); var arr = [1, 2, 3, 4,5,6,7,8,9]; console.log(subsetArray.getResult(arr,2)); 

Aquí hay una versión iterativa en python. La esencia de esto es la función increment_counters () que devuelve todas las combinaciones posibles. Sabemos que debe llamarse C (n, r) veces.

 def nchooser(n,r): """Calculate the n choose r manual way""" import math f = math.factorial return f(n) / f(nr) / f(r) def increment_counters(rc,r,n): """This is the essense of the algorithm. It generates all possible indexes. Ex: for n = 4, r = 2, rc will have values (0,1),(0,2),(0,3),(1,2),(1,3),(2,3). You may have better understanding if you print all possible 35 values for n = 7, r = 3.""" rc[r-1] += 1 # first increment the least significant counter if rc[r-1] < n: # if it does not overflow, return return # overflow at the last counter may cause some of previous counters to overflow # find where it stops (ex: in n=7,r=3 case, 1,2,3 will follow 0,5,6) for i in range(r-2,-1,-1): # from r-2 to 0 inclusive if rc[i] < i+nr: break # we found that rc[i] will not overflow. So, increment it and reset the # counters right to it. rc[i] += 1 for j in range(i+1,r): rc[j] = rc[j-1] + 1 def combinations(lst, r): """Return all different sub-lists of size r""" n = len(lst) rc = [ i for i in range(r) ] # initialize counters res = [] for i in range(nchooser(n,r)): # increment the counters max possible times res.append(tuple(map(lambda k: lst[k],rc))) increment_counters(rc,r,n) return res 

Aquí hay una versión Java de lo que creo que Simple está hablando, usando una representación binaria de todos los conjuntos en el conjunto de poder. Es similar a cómo lo hizo Abhiroop Sarkar, pero creo que una matriz booleana tiene más sentido que una cadena cuando solo representas valores binarios.

 private ArrayList> getSubsets(int m, Object[] objects){ // m = size of subset, objects = superset of objects ArrayList> subsets = new ArrayList<>(); ArrayList pot = new ArrayList<>(); int n = objects.length; int p = 1; if(m==0) return subsets; for(int i=0; i<=n; i++){ pot.add(p); p*=2; } for(int i=1; i=0; j--){ int currentPot = pot.get(j); if(y >= currentPot){ binArray[j] = true; y -= currentPot; sum++; } if(y<=0) break; } if(sum==m){ ArrayList subsubset = new ArrayList<>(); for(int j=0; j < n; j++){ if(binArray[j]){ subsubset.add(objects[j]); } } subsets.add(subsubset); } } return subsets; } 

Si está buscando la respuesta del patrón Iterator, aquí está.

 public static  Iterable> getList(final Iterable list) { List> listOfList = new ArrayList<>(); for (T t: list) listOfList.add(Collections.singletonList(t)); return listOfList; } public static  Iterable> getIterable(final Iterable list, final int size) { final List vals = new ArrayList<>(); int numElements = 0; for (T t : list) { vals.add(t); numElements++; } if (size == 1) { return getList(vals); } if (size == numElements) { return Collections.singletonList(vals); } return new Iterable>() { @Override public Iterator> iterator() { return new Iterator>() { int currPos = 0; Iterator> nextIterator = getIterable( vals.subList(this.currPos + 1, vals.size()), size - 1).iterator(); @Override public boolean hasNext() { if ((this.currPos < vals.size()-2) && (this.currPos+size < vals.size())) return true; return false; } @Override public List next() { if (!nextIterator.hasNext()) { this.currPos++; nextIterator = getIterable(vals.subList(this.currPos+1, vals.size()), size-1).iterator(); } final List ret = new ArrayList<>(nextIterator.next()); ret.add(0, vals.get(this.currPos)); return ret; } }; } }; }