combinations_of_array_v1.c

/*

    combinations_of_array_v1.c

https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

Combinations without repetition

Combination without repetition of length k over n elements
is a subset of size k of the set of size n.

A combination without repetition of length k over n elements has

(n over k) = n! / ( k! (n-k)! )

As an example, all combinations are listed below
length 3 over 5 elements (from number 1 to number 5):

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5

    You can find all my C programs at Dragan Milicev's pastebin:

    https://pastebin.com/u/dmilicev

*/

#include <stdio.h>
#include <stdlib.h>

// Prints an array a[] of length n
void print_array(int a[], int n){
    for (int i=0; i<n; i++)
        printf("%3d", a[i]);
    printf("\n");
}

// Calculates and returns the factorial of the natural number n, n! = 1*2*3*...*n
int factorial(int n){
    int factorial=1;

    for (int i=1; i<=n; i++)
        factorial = factorial * i;

    return( factorial );
}

/*
arr[]       ---> Input Array
data[]      ---> Temporary array to store current combination
start & end ---> Starting and Ending indexes in arr[]
index       ---> Current index in data[]
k           ---> Size of a combination to be printed
*/void combinationUtil(int arr[], int data[], int start, int end,
                    int index, int k)
{
    // Current combination is ready to be printed, print it
    if (index == k)
    {
        for (int j=0; j<k; j++)
            printf("%d ", data[j]);
        printf("\n");
        return;
    }

    // replace index with all possible elements. The condition
    // "end-i+1 >= k-index" makes sure that including one element
    // at index will make a combination with remaining elements
    // at remaining positions
    for (int i=start; i<=end && end-i+1 >= k-index; i++)
    {
        data[index] = arr[i];
        combinationUtil(arr, data, i+1, end, index+1, k);
    }
}

// The main function that prints all combinations of size k
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(int arr[], int n, int k)
{
    // A temporary array to store all combination one by one
    int data[k];

    // Print all combination using temporary array 'data[]'
    combinationUtil(arr, data, 0, n-1, 0, k);
}


// Program to print all combination of size k in an array of size n
int main(){
    int arr[]={1,2,3,4,5};                   // array of n integers
    int k=3, n = sizeof(arr)/sizeof(arr[0]); // combinations of length k over n elements

    printf("\n Elements are: \n\n");

    print_array(arr,n);

    printf("\n A combination without repetition of length k = %d over n = %d elements \n\n has %d and they are: \n\n\n",
           k,n, factorial(n) / ( factorial(k) * factorial(n-k) )   );

    printCombination(arr, n, k);

    printf("\n All combinations are: \n\n");

    for (int i=1; i<=n; i++)
        printCombination(arr, n, i);

} // main()