CareerCup

1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 void print(int *sets, int k)
  6 {
  7         for(int i=0; i<k; i++)
  8                 cout << sets[i] << "\t";
  9         cout << "\n";
 10 }
 11 
 12 void subsets(int A[], int n, int k, int *sets, int index, int indexA)
 13 {
 14         if(index == k)
 15         {
 16                 print(sets, k);
 17                 return;
 18         }
 19 
 20         if(indexA >= n || n-indexA < k-index)
 21                 return;
 22 
 23         sets[index] = A[indexA];
 24         subsets(A, n, k, sets, index+1, indexA+1);
 25         subsets(A, n, k, sets, index, indexA+1);
 26 }
 27 
 28 int main()
 29 {
 30         int A[] = {1,2,3,4,5};
 31 
 32         int n=5, k=3;
 33 
 34         int *sets = new int[k];
 35 
 36         subsets(A, n, k, sets, 0 , 0);
 37 
 38         delete[] sets;
 39 
 40         return 0;
 41 }

void permutation(int arry[], int n, int k)
{
int total_num_comb = pow(n,k);

for(i=0; i<total_num_comb; i++) // list all the combination
{

for(j=0; j<k; j++)
{
// elements of the set are arry[(i / pow(n,j))%5]
}
}
}
if need to remove set with same value then remove the set if all its element index value is same...
Complexcity of this code O(n*k)
but its better than recursion i guess....
thank you......

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

int k_org;
int* output;
print()
{
        int temp=0;
        for(temp=0;temp<k_org;temp++)printf("%d ",output[temp]);
        printf("\n");
}
combination(int* input,int size,int k)
{
        if(k>size)return;
        if(k==0){print(output);return;}
        int temp=0;
        for(temp=0;temp<size;temp++)
        {
                output[k-1]=input[temp];
                combination(input+temp+1,size-temp-1,k-1);
        }
}
main()
{
        int input[]={1,2,3,4,5,6,7,8};
        int size=sizeof(input)/sizeof(int);
        int k=3;k_org=k;
        output=(int*)malloc(k*sizeof(int));
        combination(input,size,k);
}

non-recursive java:

//assume valid input
int[][] getSubsets(int[] set, int length) {
  int temp = length-1; //amount of elements in each subset minus the first element
  int size = 0;
  for(int i=set.length - temp; i > 0; i--)
    size+=i;

  int[][] retSet = new int[size][length];
  
  int currset = 0;
  for(int i = 0 ; i < set.length - temp; i++) { //gets the starting element of each set
    for(int j = i+1; j<set.length; j+= length) {
       retSet[currset][0] = set[i]; //set the starting value of the current set
       for(int k=j; k<j+length; k++) {
         retSet[currset][k-j+1] = set[k]; //k-j +1 to store the second, third...etc. element in the current set
       }
       currset++;
    }
  }

public static ArrayList<ArrayList<Integer>> getAllSubSet(int num,int length){
if(length<1){
return null;
}
if(num<1){
return null;
}
if(length>num){
return null;
}
ArrayList<ArrayList<Integer>> result= new ArrayList<ArrayList<Integer>>();
for(int i=1;i!=num+1;i++){
ArrayList<Integer> tmp=new ArrayList<Integer>();
tmp.add(i);
compute_process(num,length,i+1,1,result,tmp);
}
return result;
}

public static void compute_process(int num,int len,
int curNum,int curLen,
ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> current){
if(curNum>num){
if(current.size()==len){
result.add(current);
}
return;
}
if(curLen==len){
result.add(current);
return;
}
ArrayList<Integer> next=copyList(current);
current.add(curNum);
compute_process(num,len,curNum+1,curLen+1,result,current);
compute_process(num,len,curNum+1,curLen,result,next);
}

Can be done with dynamic programming.
Basically Sol(n,k) = Sol(n-1,k) U "Sol(n-1,k-1) concat {n}"
I am attaching a recursive solution here.

def solve( n, k ) :
    if( k > n ) : return [ [] ]
    if( k == 0 ) : return [ [] ]
    if( k == n ) : return [[ x for x in range( 1, n+1 ) ]]
    return solve( n-1, k ) + [ [n] + x for x in solve( n-1, k-1 ) ]

Use Narayan Pandita's algorithm on 0000...11111 where there are n-k zeroes and k ones. It is a bit vector representation of the set.

(C++ has std::next_permutation and std::next_combination for this, I believe).

We can also write a recursive version, which uses linear amount of space (and not Theta(n^k)).

Pseudo code:

//set is the input set.
// set_len is the required length of the subset.
// so_far is the subset we have constructed so far.
// start is the starting point in the set (think of it as an array) of the unconsidered elements.
// Call as Subsets(set, empty_list, required_len, 0);
void Subsets(List set, List so_far, int set_len, int start) {
   
    if (so_far.Length == set_len) {
        printList(so_far, 0); // Print the set seen so far.
        return;
    }
    // If we have to pick the rest of elements.
    if (so_far.Length + set.Count - start == set_len) {
        printList(so_far, 0);
        printList(set, start);
        return;
    }
    
    // Add current element to set seen so far.
    so_far.Add(set[start]);
    // Recurse
    Subsets(set, so_far, set_len, start+1);
    // Don't include current element
    so_far.Remove(set[start]);
    Subsets(set, so_far, set_len, start+1);
    // so_far has been restored to what we had been called with.
}

Exercise: Modify the above recursive version to print all subsets of size less than or equal to k.

def subset(numbers, size):
    if (size == 0):
        raise Exception("size is 0")

    if size == 1:
        return [[x] for x in numbers]

    if len(numbers) < size:
        raise Exception("Invalid: len(%s) < size(%d)" % (str(numbers), size))

    if len(numbers) == size:
        return [numbers]

    first = numbers[0]
    rest = numbers[1:]

    ss = subset(rest, size-1)
    [x.append(first) for x in ss]

    ss2 = subset(rest, size)
    ss.extend(ss2)

    return ss

public static void main(String[] args) {
		ArrayList<ArrayList<Integer>> ss = subsets(5, 2);
		for(ArrayList<Integer> s : ss){
			for(Integer i : s)
				System.out.print(i + " ");
			System.out.println();
		}
	}
	
	private static ArrayList<ArrayList<Integer>> subsets(int n, int k){
		ArrayList<ArrayList<Integer>> ss;
		if(k == 1){
			ss = new ArrayList<ArrayList<Integer>>();
			for(int i=1;i<=n;i++){
				ArrayList<Integer> s = new ArrayList<Integer>();
				s.add(i);
				ss.add(s);
			}
			return ss;	
		}else{
			ArrayList<ArrayList<Integer>> newss = new ArrayList<ArrayList<Integer>>();
			ss = subsets(n, k-1);
			for(ArrayList<Integer> s : ss){
				for(int i = s.get(s.size() - 1) + 1; i <= n; i++){
					ArrayList<Integer> news = (ArrayList<Integer>) s.clone();
					news.add(i);
					newss.add(news);
				}
			}
			return newss;
		}
	}

void f(int* arr, int* buf, int k, int arr_cur, int buf_cur)
{
   if(k==0)
   {
      printf(buf);
      return;
   }

   for(int i=arr_cur;i<len(arr)-k+1;++i) 
   {
      buf[buf_cur]=arr[i];
      f(arr, buf, k-1, i+1, buf_cur+1);
   }
}

void mainfunc(int* arr, int k)
{
   int* buf = new int[k];
   f(arr, buf, k, 0, 0);
}

#include <iostream>
using namespace std;
const int MAX = 1000;
int a[MAX];
bool b[MAX];
void f1(int n, int k, int indexn, int indexk){
	int i, j;
	for(i = indexn; i <= n - k + indexk; i++){
		if(!b[i]) {
			b[i] = true;
			a[indexk] = i;
			if(indexk == k) {
				for(j = 1; j <= k; j++) {
					printf("%d ", a[j]);
				}
				printf("\n");
			} else {
				f1(n, k, indexn + 1, indexk + 1);
			}
			b[i] = false;
		}
	}
}
void f(int n, int k) {
	int i; 
	for(i = 1; i <= n; ++i) {
		a[i] = i;
		b[i] = false;
	}
	f1(n, k, 1, 1);
}
int main() {
	f(4,2);
	return 0;
}

<?php

    function myprint($index,$max,$deep,$max_deep,$array) {
        if($deep == $max_deep) {
            echo "{";
            $flag = false;
            foreach($array as $value) {
                if($flag === true)
                    echo ",";
                $flag = true;
                echo $value;
            }
            echo "}\n";
        }
        for($id = $index+1; $id <= $max ;$id ++) {
            $array []= $id;
            myprint($id,$max,$deep+1,$max_deep,$array);
            array_pop($array);
        }
    }
    myprint(0,10,0,2,array());
?>

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

void print_comb(string temp,int i,int j,int k)
{
	if(j-i+1<k ||  k==0)
	{
		cout << temp<<endl;
		return;
	}
	char ch[50];
	string rem=temp;
	for(int a=i;a<=j-k;a++)
	{
		sprintf(ch,"%d",a);
		temp=rem;
		temp+=ch;
		print_comb(temp,a+1,j,k-1);
	}
}

int main()
{
	int n,k;
	cout << "Enter n : ";
	cin >> n;
	cout << "Enter k : ";
	cin >> k;
	print_comb("",1,n,k);
	return 0;
}

def rec(arr, current_set, index, size)
    return if (index >= arr.length)

    if (current_set.length == size)
        puts current_set.to_s
        return
    end
    
    current_set.push(arr[index])
    rec(arr, current_set, index+1, size)
    current_set.pop
    
    rec(arr, current_set, index+1, size)
end

rec((1..n).to_a, [], 0, k)

#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <vector>

using namespace std;

vector<vector<int> > calcCombinations(vector<int> ip){
vector<vector<int> > op;
if(ip.size() <= 2){
op.push_back(ip);
return op;
}

vector<int> res;
while(ip.size() > 0){
int num = ip.back();
ip.pop_back();
for(int j = 0; j<ip.size(); j++){
res.clear();
res.push_back(num);
res.push_back(ip[j]);
op.push_back(res);
}
}

return op;
}

int main(){
int input[] = {16, 25, 30, 5, 7};
vector<int> ip(input, input + sizeof(input)/sizeof(int));
vector<vector<int> > op = calcCombinations(ip);
int num1, num2;
vector<int> res;
while(!op.empty()){
res = op.back();
op.pop_back();
num1 = res.back();
res.pop_back();
num2 = res.back();
res.pop_back();
cout<<num1<<", "<<num2<<endl;
}
getch();
return EXIT_SUCCESS;
}

Rather than generating all subsets in 2^n time we can do an C(n, k) algorithm for k size subset generation

HashSet<HashSet<Integer>> allSetSizeK(int[] A, int k) {
		boolean[] M = new boolean[A.length];
		HashSet<HashSet<Integer>> result = new HashSet<HashSet<Integer>>();
		setSizeK(result, A, 0, 0, k, M);
		return result;
}

void setSizeK(HashSet<HashSet<Integer>> result, int[] A, int count, int index, int k, boolean[] M) {
		if (count == k) {
			HashSet<Integer> h = new HashSet<Integer>();
			for (int i = 0; i < index; i++) {
				if (M[i])
					h.add(A[i]);
			}
			result.add(h);
			return;
		}
		if (index == A.length)
			return;

                M[index] = true;
		setSizeK(result, A, count + 1, index + 1, k, M);
		M[index] = false;
		setSizeK(result, A, count, index + 1, k, M);
}

def subsets(a, k):
    def subsets(a, sol, k):
        if k == 0:
            print sol
        for i in range(0, len(a)):
            newsol = sol + [a[i]]
            subsets(a[i + 1:], newsol, k - 1)
    subsets(a, [], k)

Here is my answer. For each element of the array, we have two options, use it or not use it. So we can use an additional array to store the options.

public static void findSubSet(int[] n, int k){
	boolean[] usedIndex = new boolean[n.length];
	print(n, k , usedIndex, 0, 0);
}
private static void print(int[] n, int k, boolean[] usedIndex, int currentSize, int startIndex) {
	if(currentSize == k) {
		System.out.print("{");
		for(int i = 0; i < n.length; i++) {
			if(usedIndex[i])
				System.out.print(n[i]+" ")
		}
		System.out.print("}");
		System.out.println();
		return;
	}
	if (startIndex == n.length)
		return;
	// first option, we use the current item
	usedIndex[startIndex] = true;
	print(n, k, usedIndex,  currentSize+1, startIndex+1);
	// Second option, we don't use the current item
	usedIndex[startIndex] = false;
	print(n, k , usedIndex, currentSize, startIndex+1);	
}

public static void subset(List<Integer> list, int n, int k, int count, int cursor, int cursor2, int[] result)
    {
	if (cursor >= k)
	{
	    if (count == k)
	    {
		System.out.println(Arrays.toString(result));
	    }
		
	    return;
	}
	
	for (int i = cursor2; i < n; i++)
	{
	    result[cursor] = list.get(i);
	    subset(list, n, k, count+1, cursor+1, i+1, result);
	}
    }

#include<iostream>
using namespace std;
void permutation(char *A,char *x,int k,int m){
int i;
if (k==m){
x[k]='\0';
cout<<x<<"\t";
}
else{
for(i=0;A[i]!='\0';i++) {
x[k]=A[i];
permutation(A,x,k+1,m);
}
}
}
int main(){
char A[]={'1','3','a','s','t','i','\0'};
char x[5];
int k,m=4;
permutation(A,x,1,m);
return 0;
}

#include<iostream>
using namespace std;
void permutation(char *A,char *x,int k,int m){
int i;
if (k==m){
x[k]='\0';
cout<<x<<"\t";
}
else{
for(i=0;A[i]!='\0';i++) {
x[k]=A[i];
permutation(A,x,k+1,m);
}
}
}
int main(){
char A[]={'1','3','a','s','t','i','\0'};
char x[5];
int k,m=4;
permutation(A,x,1,m);
return 0;
}