сгенерировать все подмножества размера k из набора

Question

Я хочу сгенерировать все подмножества размера k из набора.

например: -say У меня есть набор из 6 элементов, я должен перечислить все подмножества, в которых мощность элементов 3.

Я попытался ищет решения, но те фрагменты кода. Это было давно, так как я сделал кодирование, поэтому мне сложно понять код и построить вокруг него исполняемую программу.

Полная исполняемая программа на C или C++ будет полезна. В ожидании оптимального решения с использованием рекурсии.

Answer 1

#include <cstdio> 
void g(int s[],int p,int k,int t[],int q=0,int r=0) 
{ 
    if(q==k) 
    { 
     for(int i=0;i<k;i++) 
      printf("%d ",t[i]); 
     printf("\n"); 
    } 
    else 
    { 
     for(int i=r;i<p;i++) 
     { 
      t[q]=s[i]; 
      g(s,p,k,t,q+1,i+1); 
     } 
    } 
} 

main() 
{ 
    int s[]={1,2,3,4,5},t[5]; 
    g(s,5,3,t); 
} 

Answer 2

Инициализировать массив битов с (1<<nbits)-1, а затем использовать этот алгоритм:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Для множеств больше, чем максимальный размер целого числа, вы можете применить тот же алгоритм для вашего собственного типа.

Answer 3

Самый интуитивный алгоритм действительно будет использовать рекурсию. Когда у вас есть набор, мы предположим, что вы можете перебирать все его элементы.

Если я вызываю tail (e) набор всех элементов после элемента e.

Таким образом, я хочу прямо сейчас комбинации (с, к)

цикл по каждому элементу х и получить е :: комбинации (хвост (е), к-1), где :: означает «конкатенации к каждому из "

Конечно, иногда таких комбинаций не будет (вы не в конце списка).

Вам просто нужен мастер набор (набор наборов), чтобы добавить ваши комбинаций и способ создания

Так предполагая, у нас нет глобал везде, где мы можем иметь что-то вроде:

getCombinations(headset [in], tailset [in], count [in], output [append]) 

гарнитуры или tailset может быть пустым. count может быть 0, и в этом случае мы пишем «headset» для вывода (базовое условие), иначе мы перебираем каждый элемент в tailset, добавляем его (локально) в гарнитуру, делаем хвост (локально) хвостом нашего элемента, вычитаем 1 от count и «recurse», вызывая функцию.

Answer 4

Найти рабочий код ниже

#include<iostream> 
#include<string> 
#include<list> 

using namespace std; 

void print(list<int> l){ 
    for(list<int>::iterator it=l.begin(); it!=l.end() ; ++it) 
      cout << " " << *it; 
    cout<<endl; 
} 

void subset(int arr[], int size, int left, int index, list<int> &l){ 
    if(left==0){ 
     print(l); 
     return; 
    } 
    for(int i=index; i<size;i++){ 
     l.push_back(arr[i]); 
     subset(arr,size,left-1,i+1,l); 
     l.pop_back(); 
    } 

}  

int main(){ 
    int array[5]={1,2,3,4,5}; 
    list<int> lt; 
    subset(array,5,3,0,lt); 


    return 0; 
} 

Answer 5

Вот некоторые псевдокод. Вы можете вырезать одни и те же рекурсивные вызовы, сохраняя значения для каждого вызова по ходу и до того, как будет рекурсивный вызов, если значение вызова уже присутствует.

Следующий алгоритм будет иметь все подмножества, исключая пустое множество.

list * subsets(string s, list * v){ 
    if(s.length() == 1){ 
     list.add(s);  
     return v; 
    } 
    else 
    { 
     list * temp = subsets(s[1 to length-1], v);  
     int length = temp->size(); 

     for(int i=0;i<length;i++){ 
      temp.add(s[0]+temp[i]); 
     } 

     list.add(s[0]); 
     return temp; 
    } 
} 

Answer 6

Проблема может быть решена с использованием рекурсии. Нам нужно рассмотреть следующие случаи рекурсии.

1. Текущий элемент выбран.Теперь мы рекурсивно выберем оставшихся элементов k-1 из оставшегося набора. (Включение)
2. Текущий элемент не выбран. Теперь мы рекурсивно выбираем k элементов из оставшегося набора. (Исключение)

Ниже приведена программа на C++, которая демонстрирует вышеуказанный алгоритм.

#include<iostream> 
#include<cstdio> 

using namespace std;  

void KSubset(int *a,int n,int *s,int sindex,int index,int k){ 

    if (index>n) 
     return; 

    if (k==0){ 
     for(int i=0;i<sindex;i++) 
      printf(" %d ",s[i]); 
     printf("\n"); 
     return ; 
     } 

    s[sindex]=a[index]; 
    KSubset(a,n,s,sindex+1,index+1,k-1); 
    KSubset(a,n,s,sindex,index+1,k); 
} 


int main(){ 

    int a[]={1,2,3,4,5}; 
    int s[3]; 
    KSubset(a,5,s,0,0,3); 

    return 0; 
} 

Answer 7

#include <stdio.h> 
#define FIN "subsets.in" 
#define FOUT "subsets.out" 
#define MAXSIZE 100 

void performSubsets(int n, int k){ 

int i, j, s, v[ MAXSIZE ]; 

freopen(FOUT, "w", stdout); 


memset(v, 0, sizeof(v)); 

do { 

    v[ n - 1 ]++; 

    for(i = n - 1; i >= 1; i--) { 

     if(v[ i ] > 1) { 

      v[ i ] -= 2; 

      v[ i - 1 ] += 1; 
     } 
    } 

    s = 0; 

    for(j = 0; j < n; j++) s += v[j]; 

    for(j = 0; j < n; j++) 

     if(v[ j ] && s == k) printf("%d ", (j + 1)); 

    if(s == k) printf("\n"); 

} while(s < n);  

fclose(stdout);  

} 

int main() { 

    int n, k; 

    freopen(FIN, "r", stdin); 

    //read n and size k 
    scanf("%d %d", &n, &k); 

fclose(stdin); 

performSubsets(n,k); 

} 

Эта проблема может быть решена с помощью алгоритма нерекурсивную.