Epic Systems Interview Question
Country: United States
This is an extension of string permutation; Please see my code:
#include <stdio.h>
int numPerm(unsigned char *pNum, unsigned int wordLen, unsigned int permLen, char* pOrig)
{
unsigned char *pTemp;
unsigned int count;
unsigned char temp;
if(NULL==pNum || NULL==pOrig)
return -1;
if(!permLen)
{
temp=pNum[0];
pNum[0]='\0';
printf("%s\n", pOrig);
pNum[0]=temp;
}
for(count=0;count< wordLen;count++)
{
temp=pNum[0];
pNum[0]=pNum[count];
pNum[count]=temp;
numPerm(pNum+1, wordLen-1, permLen-1, pOrig);
pNum[count]=pNum[0];
pNum[0]=temp;;
}
return 0;
}
int main()
{
unsigned char numList[]={'0', '1', '2', '3', '4','5', '6', '7', '8', '9'};
numPerm(numList, 10, 4, numList);
}
Python version. Working code.
"""
Length is given as input.Print all possible permutations of numbers between 0-9.
Eg: if input length=4
all possible combinations can be 0123, 1234, 5678,9864,...etc all combinations of length from in all numbers between 0-9
"""
class NumPerm(object):
def __init__(self, length):
if length is None or type(length) != type(1):
print 'Invalid Length'
return False
self._length = length
self._out = []
self._src = [str(x) for x in range(10)]
self._flag = [False] * 10
def permute(self, pos = 0):
if pos == self._length:
print ''.join(self._out)
return
for i in range(len(self._src)):
if self._flag[i] is True:
continue
self._out.append(self._src[i])
self._flag[i] = True
self.permute(pos + 1)
self._out.pop()
self._flag[i] = False
if __name__ == '__main__':
n = NumPerm(3)
n.permute()
public class StringPremutation {
public static void permutation(int[] base,int n,int perlength,int[] perm)
{
int temp;
if(n==0)
{
for(int i=0;i<4;i++)
{
System.out.print(perm[i]);
}
System.out.println();
}
else
{
for(int count=4-n;count<perlength;count++)
{
temp=perm[0];
perm[0]=perm[count];
perm[count]=temp;
permutation(base,n-1,perlength,perm);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] base={0,1,2,3,4,5,6,7,8,9};
int[] perm=new int[10];
perm=base;
permutation(base,4,10,perm);
}
}
use recursion, divide and conquer
Time complexity:T(n)=10T(n-1)+O(1)
T(n)=O(10^n)
This is simple. but not the best in algorithms, does anyone have better idea?
Just wondering, if we have to generate all permutations of length n with 0-9 digits, then isn't it equal to generating all the numbers from 0 to X where x is the maximum number possible of length n (n = 4, x = 9999).
If this is the case then just generate max number in one loop as string (Append n times 9 to X). Make another loop from 0 to X and print numbers left padded with 0 upto length n.
If my understanding is correct then as per my comment on previous post, here is the code. Please correct me if I understood it wrong
public static void generateAllPerm(int n) {
if (n == 0) {
System.out.println("None possible");
return;
}
String x = new String();
for (int i = 0; i < n; i++) {
x += "9";
}
int iX = Integer.parseInt(x);
for (int i = 0; i <= iX; i++) {
System.out.println(String.format("%0" + n + "d",i));
}
}
A super naive algorithm is to count from 0000 to 9999, and just skip over any number with duplicate digits. Over half of the numbers (5040) are valid candidates, so it's not horribly wasteful. Then you think about it some more, and you realize every number from 7700 to 7799 is a "bad" number, so you can detect numbers of the form nn00, and immediately skip past 100 values. Pretty soon you'll converge on what's essentially an odometer algorithm. When you roll the odometer, instead of incrementing the current digit, increment to the next digit not already used by a higher digit. You can micro-optimize digit detection by having a length ten map of which numbers are available.
Python Successor Approach
This is a mostly iterative approach toward generating the permutations. It introduces a successor function, which perhaps simulates better how a human would approach the problem--we have a number, and we want to find the next viable candidate.
# Generating permutations is a fun challenge,
# but it's also nice to have a successor function
# that can just give you the next permutation.
def permutations(num_digits):
n = 0
for i in range(num_digits):
n = n * 10 + i
bitmap = make_bitmap(num_digits, n)
while n:
yield n
n = successor_helper(num_digits, n, bitmap)
# This is for one stop shopping.
def successor(num_digits, n):
bitmap = make_bitmap(num_digits, n)
return successor_helper(num_digits, n, bitmap)
# If you want successive permutations, call the
# successor_helper with a bitmap.
def successor_helper(num_digits, n, bitmap):
ones = n % 10
tens = n / 10
bitmap[ones] = False
for ones in range(ones+1, 10):
if not bitmap[ones]:
bitmap[ones] = True
return tens * 10 + ones
# we overflowed
if num_digits == 1:
return None
tens = successor_helper(num_digits-1, tens, bitmap)
if not tens:
return None
for ones in range(10):
if not bitmap[ones]:
bitmap[ones] = True
return tens * 10 + ones
return None
def make_bitmap(num_digits, n):
bm = [False] * 10
for i in range(4):
bm[n % 10] = True
n /= 10
return bm
def test():
def test_successor(n, exp_new_n):
bm = make_bitmap(4, n)
new_n = successor_helper(4, n, bm)
assert new_n == exp_new_n
assert bm == make_bitmap(4, new_n)
test_successor(123, 124)
test_successor(132, 134)
test_successor(139, 142)
test_successor(189, 192)
test_successor(198, 213)
test_successor(1987, 2013)
assert 213 == successor(4, 198)
assert successor(4, 9876) is None
assert 9 * 10 == len(list(permutations(2)))
assert 7 * 8 * 9 * 10 == len(list(permutations(4)))
test()
My understanding is to simply print all the number from 0 to the maximum value that is calculated from the digit.
static void allCombo(int digit){
int maxVal = (int)Math.pow(10, digit);
int num_of_zero;
StringBuffer sb = new StringBuffer();
for(int i=0;i<maxVal;i++){
if(i==0){
for(int k=0;k<digit;k++){
sb.append('0');
}
System.out.println(sb);
sb.delete(0, sb.length()+1);
continue;
}
num_of_zero = digit - ((int)Math.log10(i)+1); //the number of 0 that hold the digit
for(int j=0;j<num_of_zero;j++){
sb.append('0');
}
sb.append(i);
System.out.println(sb);
sb.delete(0,sb.length()+1);
}
}
Easy Peasy Python one:
def permute(digit):
if digit == 0:
print "Sorry, this is not going to work."
else:
digitnum = str(9)
for elem in range(digit-1):
digitnum += str(9)
digitnum = int(digitnum)+1
#print digitnum
for j in range(1,digitnum,+1):
print str(j),
while True:
try:
digit = int(raw_input('Enter the input length: \n'))
break
except ValueError:
print 'Please type only numbers'
permute(digit)
using recursion
public class allNumComb {
public static void getComb(String in, String c, int r) {
if (r == 0)
System.out.println(c);
else if (in.length() != 0) {
getComb(in.substring(1, in.length()), c+in.charAt(0), r-1);
getComb(in.substring(1, in.length()), c, r);
}
}
public static void main (String args[]) {
String inp = "0124";
getComb(inp, "", 2);
}
}
package epic;
public class PermutationsNumber {
public static void main(String[] args) {
String s = "0123456789";
int leng = 4;
printPerm(s, leng, "");
}
private static void printPerm(String s, int leng, String re) {
if (leng == 1) {
for (int l = 0; l < s.length(); l++) {
System.out.println(re + s.substring(l, l + 1));
}
} else {
for (int i = 0; i < s.length(); i++) {
String s2 = s.substring(0, i) + s.substring(i + 1, s.length());
String re2 = re + s.substring(i, i + 1);
printPerm(s2, leng - 1, re2);
}
}
}
}
package epic;
public class permution {
public static void main(String args[])
{
String base = "0123456789";
permute(4,"",base);
}
public static void permute(int length, String s, String base)
{
if(length == 0)
System.out.println(s);
else
{
for(int i = 0; i < base.length();i++)
permute(length-1,s + base.charAt(i),base);
}
}
}
#include <stdio.h>
void swap(char *a, char *b) {
char temp = *a;
*a= *b;
*b = temp;
}
void permute(char *str, int start, int end, int size) {
int i = 0;
if(start == size) {
int j = 0;
for(j = 0 ; j < start ; j++) {
printf("%c", str[j]);
}
printf("\n");
}
else {
for(i = start ; i <= end ; i++) {
swap(&str[start], &str[i]);
permute(str, start+1, end,size);
swap(&str[start], &str[i]);
}
}
}
int main() {
char str[]={'0','1','2','3','4','5','6','7','8','9'};
permute(str, 0, 9, 4);
return 0;
}
Guys, please correct me if i misunderstood the question -
permutation in general means an arrangement. So if we want to generate a number with length 4, from (0..9), this means each position will have 9 possible values. So it means total number of possible values is 9 * 9 * 9 * 9. correct?
if yes, then we can put 4 for loops with indexes, i j k l and print "[i][j][k][l]".
Is this right?
#include<iostream>
using namespace std;
void printArr(int arr[],int n)
{
bool yes[10]={false}
for(int i=0;i<n;i++)
{
if(yes[arr[i]]==false)yes[i]=true;
else if(yes[arr[i]]==true)return;
}
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
}
void permsUtil(int arr[],int n,int pos)
{
if(pos==n){printArr(arr,n);return;}
if(pos==0)
{
for(int i=0;i<=9;i++){
arr[pos]=i;
permsUtil(arr,n,pos+1);
}
}
else{
for(int i=0;i<=9;i++)
{
if(i==arr[pos-1])continue;
arr[pos]=i;
permsUtil(arr,n,pos+1);
}
}
}
void perms(int n)
{
int arr[n];
permsUtil(arr,n,0);
}
int main()
{
perms(4);
return 0;
}
In java, the code works fine.
public class Permutations {
public static void main(String[] args) {
int[] array = new int[]{0, 1, 2, 3, 4, 6};
permutation(0,array,3,3) ;
}
static void permutation(int num, int[] array, int n, int size) {
int start;
int digit;
if (n == size)
start = 1;
else
start = 0;
for (int i = start; i < array.length; i++) {
digit = (int) (array[i] * Math.pow(10, n - 1));
if (n == 1)
System.out.println(num+digit);
else
permutation(num+digit, array, n - 1, size);
}
}
# include <iostream>
# include <math.h>
# include <stdlib.h>
# include <sstream>
using namespace std;
bool check(string product){
int length=product.size();
for (int l=0; l <length; l++){
for(int h=l+1;h<length;h++){
if (product[l]==product[h]){
return false;
break;
}
}
}
return true;
}
void permutation(string k, int m){
for (int i = 0; i < pow(10,m); ++i)
{
string product; stringstream ss;
string temp="";
ss<<i;
k=ss.str();
int len=k.size();
for(int j=1; j<=m-len; j++){
temp="0"+temp;
}
product=temp+k;
if (check(product)==true)
{
cout<<"The numbers are: "<<product<<endl;
}
}
}
int main(int argc, char const *argv[])
{
cout<<"Please type the length of the number: "<<endl;
int n;
cin>>n;
permutation("", n);
return 0;
}
This could be written in simple and concise code with recursion. Basic idea is to flip the digit one by one starting from the digit left to it plus 1 to 9, then recurse to the right. See commented Java code below.
/**
* Recursive method to generate combinations or print the number
* @param number The current array of digits
* @param index The current index where the digit is "flipping"
*/
private static void printCombinations(int[] number, int index) {
// The number to start flipping. Say we have 35**, then the
// first * should start from 6 to 9.
int start = 0;
if(index >= 1) {
start = number[index - 1] + 1;
}
// Loop to flip the digit
for(int i = start; i <= 9; i++) {
number[index] = i;
// If at the end of the array, print it out
if(index == number.length - 1) {
printArray(number);
} else { // Recurse to the right
printCombinations(number, index + 1);
}
}
}
// Print the digits out
private static void printArray(int[] arr) {
for(int i : arr) {
System.out.print(String.valueOf(i));
}
System.out.println();
}
// Entry method
public static void printCombinations(int n) {
if(n < 1) {
return;
}
int[] number = new int[n];
printCombinations(number, 0);
}
public static void main(String[] args) {
printCombinations(4);
}
#include <iostream>
#include <string>
using namespace std;
void printPermutation(string src, string set, int numLeft) {
if (numLeft == 0) {
cout << src << endl;
return;
}
for (int i = 0; i < set.length(); ++i) {
printPermutation(src + set[i], set.substr(0, i) + set.substr(i + 1, set.length() - i - 1), numLeft - 1);
}
}
void main() {
printPermutation("", "0123456789", 2);
cin.get();
}
package p1;
import java.util.Scanner;
public class permutation {
public static void main(String arg[])
{
Scanner keyboard = new Scanner(System.in);
System.out.println("enter an integer from keyboard and press enter");
int myint = keyboard.nextInt();
System.out.println(myint);
int[] num=new int[myint];
int p=0;
perm(num,p);
}
static void perm(int[] num,int p)
{
for(int i=p;i<num.length;i++)
{
for(int j=0;j<10;j++)
{
num[i]=j;
perm(num,i+1);
}
}
for(int i=0;i<num.length;i++){
for(int j=0;j<num.length;j++)
{
System.out.print(num[j]);
}
System.out.println();
}
}
}
If I am understanding this correctly, the string cannot have the same digit. Then this is pretty simple. Just use a DFS and check for duplication. Below is my code in JAVA:
public class print_permutation{
public static void print(int num)
{
StringBuilder sb = new StringBuilder();
DFS(num,sb);
}
public static void DFS(int num, StringBuilder sb)
{
if(num==0)
{
System.out.println(sb.toString());
return;
}
for(int i=0;i<=9;i++)
{
if(sb.indexOf(i+"")>=0) continue;
sb.append(i+"");
DFS(num-1,sb);
sb.deleteCharAt(sb.length()-1);
}
}
public static void main(String[] args)
{
print(4);
}
}
public static void printperm(String number, int prev, int n, int cons) {
if (n == 0) {
if (number.length() < cons) {
number = "0" + number;
}
System.out.println(new StringBuilder(number).reverse().toString());
System.out.println(number);
return;
}
for (int i = prev + 1; i < 11 - n; i++) {
int num = Integer.valueOf(number) * 10 + i;
printperm(String.valueOf(num), i, n - 1, cons);
}
}
#include<iostream.h>
#include<conio.h>
#include<math.h>
void main()
{
clrscr();
int a,i,b,count=0;
cout<<"Enter the no of digits";
cin>>a;
b=pow(10,(a-1))
for(i=a;i<(pow(10,a));i++)
{
cout<<i;
cout<<"\n";
count++;
}
cout<<"total no of available digits is";
cout<<count;
getch();
}
I felt that recursion is more natural so that's what I used.
- e_carg March 22, 2013class PrintPermutation { public static void main(String[] args) { print("", "012345", 4); } private static void print(String res, String digits, int n) { if (n == 0) System.out.println(res); for (int i = 0; i < digits.length(); ++i) { print(res + digits.charAt(i), digits.replace(String.valueOf(digits.charAt(i)), ""), n - 1); } } }