## Cadence Inc Interview Question

SDE1s**Country:**India

**Interview Type:**In-Person

given a array of digits. print all combination of of these i.e all no formed by these.

repetition allowed.

and then for modification:

repetition not allowed

example:

i/p:

arr={2,3,4}

o/p:

(without repetition)

234

243

324

342

423

432

========

Your example, if repetition was allowed, what would the o/p be?

Type your questions clearly. These are permutations not combinations.

```
def permute(xs):
"""Generate all permutations of `xs`
Example:
>>> list(permute([0, 1, 2]))
[[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]]
"""
if len(xs) <= 1:
yield xs
return
h, ts = xs[0], xs[1:]
for t in permute(ts):
for i in range(len(ts) + 1):
yield t[:i] + [h] + t[i:]
```

void permute(int *a, int i, int n)

{

int j,k;

if (i == n)

{

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

printf("%d", a[k]);

printf("\n");

}

else

{

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

{

swap((a+i), (a+j)); //Here swap function will swap the value of its

permute(a, i+1, n);

swap((a+i), (a+j)); //Here swap function will swap the value of its

}

}

}

main()

{

int a[] = {1,2,3};

permute(a,0,2);

}

int swap(int *a, int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

If you use C++, the best solution is to use std::next_permutation:

```
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
int n = 0;
std::cin >> n;
std::vector<int> nums(n);
for(int i = 0; i < n; i++)
std::cin >> nums[i];
std::sort(nums.begin(), nums.end());
do
{
for(int i = 0; i < n; i++)
std::cout << nums[i];
std::cout << std::endl;
}
while(std::next_permutation(nums.begin(), nums.end()));
return 0;
}
```

#include <iostream>

using namespace std;

bool isValid0(int out[], int size) {

for (int i = 0; i < size; ++i) {

for (int j = i + 1; j < size; ++j) {

if (out[i] == out[j]) return false;

}

}

return true;

}

void auxPerm0(int d, int in[], int out[], int size) {

if (d == size) {

if (isValid0(out, size))

{

for (int i = 0; i < size; ++i)

cout << out[i] << " ";

cout << endl;

}

return;

}

for (int i = 0; i < size; ++i) {

out[d] = in[i];

auxPerm0(d + 1, in, out, size);

}

}

void permutations0(int in[],int size) {

int *out = new int[size];

auxPerm0(0, in, out, size);

}

int main()

{

int ar[] = { 2,3,4 };

int n = sizeof(ar) / sizeof(ar[0]);

permutations0(ar,n);

return 0;

}

This is permutation problem where we need to form the number with all the digit given in the array. Below is the working code for the same.

Call the function with "permute(arr, 0, sizeOfArray);"

- Rahul September 23, 2013