Trova tutti i sottoinsiemi di lunghezza k in un array

Question

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

Ad esempio, se n = 4 ek = 2, output è {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

Non riesco nemmeno a capire come iniziare. Non è necessario utilizzare le funzioni della libreria incorporata come next_permutation, ecc.

È necessario l'algoritmo e l'implementazione in C/C++ o Java.

Answer 1

La ricorsione è tuo amico per questo compito.

Per ogni elemento: "indovina" se si trova nel sottoinsieme corrente e richiama ricorsivamente con l'ipotesi e un superset più piccolo da cui è possibile selezionare. Farlo per entrambe le ipotesi "sì" e "no" comporterà tutti i possibili sottoinsiemi.
Il trattenimento di una certa lunghezza può essere facilmente eseguito in una clausola di arresto. Codice

Java:

private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> 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<Set<Integer>> getSubsets(List<Integer> superSet, int k) { 
    List<Set<Integer>> res = new ArrayList<>(); 
    getSubsets(superSet, k, 0, new HashSet<Integer>(), res); 
    return res; 
} 

Invocare con:

List<Integer> 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]] 

Answer 2

Utilizzare una rappresentazione vettore di bit del set, e utilizzare 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.

Answer 3

Partenza 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<String> x; 
    int n=4; 
    int k=2; 
    int arr[]={1,2,3,4}; 
    StringBuilder sb=new StringBuilder(); 
    for(int i=1;i<=(n-k);i++) 
     sb.append("0"); 
    for(int i=1;i<=k;i++) 
     sb.append("1"); 
    String bin=sb.toString(); 
    x=generatePerm(bin); 
    Set<ArrayList <Integer>> outer=new HashSet<ArrayList <Integer>>(); 
    for(String s:x){ 
     int dec=Integer.parseInt(s,2); 
     ArrayList<Integer> inner=new ArrayList<Integer>(); 
     for(int j=0;j<n;j++){ 
      if((dec&(1<<j))>0) 
       inner.add(arr[j]); 
     } 
     outer.add(inner); 
    } 
    for(ArrayList<?> z:outer){ 
     System.out.println(z); 
    } 
} 

    public static Set<String> generatePerm(String input) 
{ 
    Set<String> set = new HashSet<String>(); 
    if (input == "") 
     return set; 

    Character a = input.charAt(0); 

    if (input.length() > 1) 
    { 
     input = input.substring(1); 

     Set<String> 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 elemento di 4 set a scopo di test e l'utilizzo di k = 2. Quello che cerco di fare è inizialmente generare una stringa binaria in cui sono impostati k bit e n-k 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.

Answer 4

Si prega di verificare la mia soluzione: -

private static void printPermutations(List<Integer> list, int subSetSize) { 
    List<Integer> prefixList = new ArrayList<Integer>(); 
    printPermutations(prefixList, list, subSetSize); 
} 

private static void printPermutations(List<Integer> prefixList, List<Integer> 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 a 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)); 
    } 
} 

Answer 5

Questo è un implemation in F #:

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

Si può provare in F # REPL:

> allSubsets 3 2;; 

val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [2; 3]] 

> allSubsets 4 2;; 

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

Questa classe Java implementa lo stesso algoritmo:

import java.util.HashSet; 
import java.util.Set; 

public class AllSubsets { 

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

Se non ti piace F # o Java quindi visitare questo sito.Essa elenca le soluzioni per il vostro problema particolare in vari linguaggi di programmazione:

http://rosettacode.org/wiki/Combinations

Answer 6

Si tratta di pitone. Ci scusiamo per gli spagnoli;)

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])) 

Answer 7

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

Answer 8

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(n-r)/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+n-r: 
      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 

Answer 9

#include<iostream> 
    #include<cstdio> 
    #include<vector> 
    using namespace std; 
    vector<int> v; 
    vector<vector<int> > result; 

    void subset(int arr[],int k,int n,int idx){ 
    if(idx==n) 
return; 

if(k==1){ 
    for(int i=idx;i<n;i++) 
    { 
     v.push_back(arr[i]); 
     result.push_back(v); 
     v.pop_back(); 
    } 
} 

for(int j=idx;j<n;j++) { 
    v.push_back(arr[j]); 
    subset(arr,k-1,n,j+1); 
    v.pop_back(); 
    } 
} 

int main(){ 
int arr[] = {1,2,3,4,5,6,7}; 
int k = 4; 
int n =sizeof(arr)/sizeof(arr[0]); 
subset(arr,k,n,0); 

for(int i = 0;i<result.size();i++) 
{ 
    for(int j = 0;j<result[i].size();j++) 
    { 
    cout << result[i][j] << " "; 
    } 
    cout << endl; 
} 
} 

Answer 10

Ecco una versione Java di quello che penso Semplice sta parlando, utilizzando una rappresentazione binaria di tutti i set nel set potere. È 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<ArrayList<Object>> getSubsets(int m, Object[] objects){ 
    // m = size of subset, objects = superset of objects 
    ArrayList<ArrayList<Object>> subsets = new ArrayList<>(); 
    ArrayList<Integer> 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<p; i++){ 
     boolean[] binArray = new boolean[n]; 
     Arrays.fill(binArray, false); 
     int y = i; 
     int sum = 0; 
     for(int j = n-1; j>=0; j--){ 
      int currentPot = pot.get(j); 
      if(y >= currentPot){ 
       binArray[j] = true; 
       y -= currentPot; 
       sum++; 
      } 
      if(y<=0) 
       break; 
     } 
     if(sum==m){ 
      ArrayList<Object> subsubset = new ArrayList<>(); 
      for(int j=0; j < n; j++){ 
       if(binArray[j]){ 
        subsubset.add(objects[j]); 
       } 
      } 
      subsets.add(subsubset); 
     } 
    } 

    return subsets; 
} 

Answer 11

Se stai cercando la risposta del modello Iterator, eccoti qui.

public static <T> Iterable<List<T>> getList(final Iterable<? extends T> list) { 

    List<List<T>> listOfList = new ArrayList<>(); 

    for (T t: list) 
     listOfList.add(Collections.singletonList(t)); 

    return listOfList; 
} 
public static <T> Iterable<List<T>> getIterable(final Iterable<? extends T> list, final int size) { 

    final List<T> 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<List<T>>() { 

     @Override 
     public Iterator<List<T>> iterator() { 
      return new Iterator<List<T>>() { 

       int currPos = 0;      
       Iterator<List<T>> 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<T> next() { 
        if (!nextIterator.hasNext()) { 
         this.currPos++; 
         nextIterator = getIterable(vals.subList(this.currPos+1, vals.size()), size-1).iterator(); 
        } 
        final List<T> ret = new ArrayList<>(nextIterator.next()); 
        ret.add(0, vals.get(this.currPos)); 
        return ret; 
       } 
      }; 
     } 
    }; 
}