Trouver tous les sous-ensembles de longueur k dans un tableau

Question

Étant donné un ensemble {1,2,3,4,5...n} de n éléments, nous devons trouver tous les sous-ensembles de longueur k .

Par exemple, si n = 4 et k = 2, les output serait {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} .

Je n'arrive même pas à savoir comment commencer. Nous n'avons pas besoin d'utiliser les fonctions de la bibliothèque intégrée comme next_permutation, etc.

J'ai besoin de l'algorithme et de sa mise en œuvre en C/C++ ou en Java.

Answer 1

La récursion est votre amie pour cette tâche.

Pour chaque élément - "devinez" s'il est dans le sous-ensemble actuel, et invoquez récursivement avec la supposition et un sur-ensemble plus petit dans lequel vous pouvez choisir. En procédant ainsi pour les suppositions "oui" et "non", vous obtiendrez tous les sous-ensembles possibles.
Se limiter à une certaine longueur peut être facilement réalisé dans une clause d'arrêt.

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

Invoquer avec :

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

Cédera :

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

Answer 2

Utilisez une représentation en vecteur de bits de l'ensemble, et utilisez un algorithme similaire à ce que std::next_permutation fait sur 0000.1111 (n-k zéros, k uns). Chaque permutation correspond à un sous-ensemble de taille k.

Answer 3

C'est Python. Désolé pour l'espagnol ;)

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 4

   #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 5

Une autre solution intéressante.

#include<bits/stdc++.h>
using namespace std;
long factorial(int n) { return (n==1|| n==0|| n < 0) ? 1 : n *factorial(n-1) ;}
void printS(int set[],int n,int k) 
{ 

   long noofsubset =  factorial(n) / (factorial(n-k)*factorial(k));
   bitset<32> z ((1 << (k)) - 1);
   string s = z.to_string();
    int i = 0;
        while(i<noofsubset)
        { 
                  for (int j = 0; j  < n;j++)
                  {
                      if(s[(32-n)+j] == '1')
                        cout << set[j]<<" ";
                  }
                    cout << endl;
                next_permutation(s.begin(),s.end());
                i++;
        } 
}

void printSubsetsOfArray(int input[], int size) {
    int k  = 3;
  printS(input,size,k)  ;
}