﻿ Thiago's website

# Permutations

February 2020

Given a string (for instance "abcd") and a group size (for instance 2) we generate all combinations.

```ab
ac
ba
bc
bd
ca
cb
cd
da
db
dc
```

Because the order matters we have for instance ab and also ba.

The number of items generate is:

```
N!
-----
(G-1)!

or

N * (N-1) * (N-2) ...

4*3 = 12

4!
----- = 12
(2-1)

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

_Bool NotUsed(int used[], int s, int index)
{
for (int i = 0; i < s; i++)
{
if (used[i] == index)
return 0;
}
return 1;
}

void f2(const char* s, int indexesUsed[], int usedCount, int count, int groupSize)
{
if (usedCount == groupSize)
{
for (int i = 0; i < usedCount; i++)
{
printf("%c", s[indexesUsed[i]]);
}
printf("\n");
return;
}
for (int i = 0; i < count; i++)
{
if (NotUsed(indexesUsed, usedCount, i))
{
indexesUsed[usedCount] = i; //insert on the set of used indexes
f2(s, indexesUsed, usedCount + 1, count, groupSize);
}
}
}

int NumCombinations(int size, int groupSize)
{
int result = 1;
for (int i = 0; i < groupSize; i++)
{
result = result * (size - i);
}
return result;
}

int main()
{
int used[8] = {-1};
f2("abcd", used, 0, sizeof("abcd") - 1, 2);
}

```

Bit set

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

void f2(const char* s,
int indexesUsed[],
int usedSet,
int usedCount,
int count,
int groupSize)
{
if (usedCount == groupSize)
{
for (int i = 0; i < usedCount; i++)
{
printf("%c", s[indexesUsed[i]]);
}
printf("\n");
return;
}
for (int i = 0; i < count; i++)
{
if (!((usedSet & (1 << i)) != 0))
{
usedSet = usedSet | (1 << i) ;
indexesUsed[usedCount] = i;
f2(s, indexesUsed, usedSet, usedCount + 1, count, groupSize);
usedSet &= ~(1 << i);
}
}
}

int NumCombinations(int size, int groupSize)
{
int result = 1;
for (int i = 0; i < groupSize; i++)
{
result = result * (size - i);
}
return result;
}

int main()```

`{ int used int usedSet = 0; f2("abcd", used, usedSet,0 , sizeof("abcd") - 1, 4); }

```
If the ordern does not matter:
From this site:
https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

```

// Program to print all combination of size r in an array of size n

# include

void combinationUtil(int arr int index, int r);

// The main function that prints all combinations of size r // in arrvoid printCombination(int arr{ // A temporary array to store all combination one by one int data

// Print all combination using temprary array 'data combinationUtil(arr, data, 0, n-1, 0, r); }

/ data start & end ---> Staring and Ending indexes in arr index ---> Current index in data r ---> Size of a combination to be printed void combinationUtil(int arr int index, int r) { // Current combination is ready to be printed, print it if (index == r) { for (int j=0; j<r; j++) printf("%d ", data printf("\n"); return; }

// replace index with all possible elements. The condition // "end-i+1 >= r-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 >= r-index; i++) { data combinationUtil(arr, data, i+1, end, index+1, r); } }

// Driver program to test above functions int main() { int arr int r = 3; int n = sizeof(arr)/sizeof(arr printCombination(arr, n, r); }