Trova tutti i sottoinsiemi di lunghezza k in un array

Dato un insieme {1,2,3,4,5...n} di n elementi, abbiamo bisogno di trovare tutti i sottoinsiemi di lunghezza k.

Ad esempio, se n = 4 ek = 2, l’ output sarebbe {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} .

Non sono nemmeno in grado di capire come iniziare. Non dobbiamo usare le funzioni di libreria integrate come next_permutation, ecc.

Serve l’algoritmo e l’implementazione in C / C ++ o Java.

La ricorsione è tuo amico per questo compito.

Per ogni elemento: “indovina” se si trova nel sottoinsieme corrente e invocando ricorsivamente con l’ipotesi e un superset più piccolo da cui è ansible selezionare. Farlo per entrambe le ipotesi “sì” e “no” comporterà tutti i possibili sottoinsiemi.
Restrinarsi a una certa lunghezza può essere facilmente fatto in una clausola di stop.

Codice 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; } 

Invocare con:

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

Produrrà:

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

Usa una rappresentazione vettoriale bit dell’insieme e usa un algoritmo simile a quello che std :: next_permutation fa su 0000.1111 (nk zero, k uno). Ogni permutazione corrisponde ad un sottoinsieme di dimensione k.

Controlla la mia soluzione

 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; } } 

Sto lavorando su un set di 4 elementi per scopi di test e usando k = 2. Quello che cerco di fare è inizialmente generare una stringa binaria in cui sono impostati k bit e nk bit non sono impostati. Ora usando questa stringa trovo tutte le possibili permutazioni di questa stringa. E poi usando queste permutazioni, emetto il rispettivo elemento nel set. Sarebbe bello se qualcuno potesse parlarmi della complessità di questo problema.

Questo è Python. Scusa per lo spagnolo;)

 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 

Per favore controlla la mia soluzione: –

 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); } } } 

Questo è simile alle permutazioni String: -

 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)); } } 

Questa è un’implementazione in 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) 

Puoi provarlo con 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]] 

Questa class Java implementa lo stesso 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; } } 

Se non ti piace F # o Java, visita questo sito. Elenca le soluzioni al tuo particolare problema in vari linguaggi di programmazione:

http://rosettacode.org/wiki/Combinations

Implementazione di 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)); 

Ecco una versione iterativa in python. Essenza di esso è la funzione increment_counters () che restituisce tutte le combinazioni possibili. Sappiamo che deve essere chiamato C (n, r) volte.

 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 

Ecco una versione Java di ciò di cui penso Simple sta parlando, usando una rappresentazione binaria di tutti gli insiemi nel set di potenza. È simile a come ha fatto Abhiroop Sarkar, ma penso che un array booleano abbia più senso di una stringa quando si rappresentano solo valori binari.

 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; } 

Se stai cercando la risposta del pattern di Iterator, eccoti qui.

 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; } }; } }; }