Cadence Inc Interview Question
SDE1sCountry: 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