I want to write a program, which given two integer inputs j and k will output the combinations of j things partitions into k groups. For instance if j=5 and k=3 the output would be
(5, 0, 0)
(4, 1, 1)
(3, 2, 0)
(3, 1, 1)
(2, 2, 0)
I've got no idea what to do. I think I should use nested loop or use recursion. Please help.
I do not think this is efficient:
int n=5;
int i,j,k;
for(i=5;i>0;i--){
for(j=4;j>=0;j--){
for(k=3;k>=0;k--){
if((i+j+k==5)&&i>=j&&j>=k){
System.out.print(i);
System.out.print(j);
System.out.println(k);
continue;
}
}
}
}
You probably solved your problem, but take a look at this class "Combinator"; it solved me a lot of problems of combinations!!!!
import java.util.* ;
public class Combinator {
public static int getFattoriale(int number){
int result=0;
if(number==0){return 1; }
if(number>0){
int fattoriale=1;
for(int i=1;i<=number;i++){
fattoriale=fattoriale*i;
}
return fattoriale;
}
return result;
}
private static List getCombinations(Object[] objs,int k){
ArrayList result=new ArrayList();
if((objs.length!=0)&& (k!=0)&&(k<=objs.length)){
//System.out.println("qui ci sono");
for(int i=0;i<objs.length;i++){
//costruisco l'array degli elementi escluso quello corrente
Object currentObj=objs;
Object[] othersObjs=new Object[objs.length-1];//dimensiono l'array degli
// altri oggetti
// inizio a riempire l'array degli altgri oggetti
int z=0;
for(int j=0;j<objs.length;j++){
if(!objs.equals(objs[j])){othersObjs[z]=objs[j];z++;}
}
//System.out.println(" Oggetto "+ i+" = "+((Integer)objs).intValue());
//String sequenza="";
//for(int y=0;y<othersObjs.length;y++){
//sequenza=sequenza+","+String.valueOf(((Integer)othersObjs[y]).intValue());
//}
//System.out.println("Gli altri oggetti da combinare sono:"+sequenza);
//try{Thread.sleep(5000);}catch(InterruptedException e){}
List othersList=getCombinations(othersObjs,k-1);//estraggo la lista delle
//k-1 uple
Iterator othersListIter=othersList.iterator();
if(othersList.size()>0){//creo l'iteratore per leggerle
while(othersListIter.hasNext()){
List currentComb=(ArrayList)othersListIter.next(); //ottengo iterattivamente
//la lista di combinazioni
currentComb.add(objs);
if(!containsCombination(result,currentComb)){result.add(currentComb);}
}
}else{
ArrayList myList=new ArrayList();
myList.add(objs);
if(!containsCombination(result,myList)){result.add(myList);}}
}
//System.out.println("Ritorno "+ result.size()+ "elementi");
return result;
}else{return result; }
}
private static boolean containsCombination(List container,List combination){
boolean result=false;
List comb=combination;
Iterator containerIter =container.iterator();
while(containerIter.hasNext()){
List combCheck=(List)containerIter.next();
if(isSameCombination(combCheck,comb)){ return true;}
}
return result;
}
private static boolean isSameCombination(List list,List otherList){
boolean result=true;
/*Iterator iterMe;*/Iterator iterOther;
iterOther=otherList.iterator();//iterMe=iterator();
while(iterOther.hasNext()){
Object currentObj=iterOther.next();
if((list.size()==otherList.size())&& (!list.contains(currentObj))){
return false;
}
}
return result;
}
public static Object[][] getArrayOfCombinations(Object[]objs,int k){
Object[][] result=null;
List combList=getCombinations(objs,k);
if(!combList.isEmpty()){
int combNumber=combList.size();
result=new Object[combNumber][k];
//riempio l'array
int i=0;
Iterator combListIter=combList.iterator();
while(combListIter.hasNext()){
List comb=(List)combListIter.next();
int j=0;
Iterator combIter=comb.iterator();
while(combIter.hasNext()){
result[j]=combIter.next();
j++;
}
i++;
}
}
return result;
}
}
