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

Question

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

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

Я пытался найти решение, но это фрагменты кода. Прошло много времени с тех пор, как я занимался кодированием, поэтому мне сложно понять код и создать из него исполняемую программу.

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

Answer 1

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

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

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

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

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

Answer 3

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

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

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

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

Answer 5

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

}

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

Answer 6

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

В следующем алгоритме будут все подмножества, кроме пустого набора.*

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 7

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

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

Таким образом, я хочу прямотеперь комбинации (s, k)

зацикливаются на каждом элементе в s и получают e :: комбинаций (tail (e), k-1), где :: означает "сцепленный с каждым из"

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

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

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

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

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