Combination with Repition, possible?
Hi experts,
I've this code and the following is the output:
class Combinationsimplements Enumeration{
privateint lo, hi, n;
privateint[] c=null;
privateint[] init(){
c=newint[n];
for (int i= 0, j= lo; i < n; c[i++]= j++);
return c;
}
privateint findPivot(){
if (c ==null)return 0;
for (int i= n; --i >= 0; )
if (c[i] <= hi-(n-i))return i;
return -1;
}
public Combinations(int lo,int hi,int n){
this.lo= lo;
this.hi= hi;
this.n = n;
}
publicboolean hasMoreElements(){return findPivot() >= 0;}
public Object nextElement(){
if (c ==null)return init();
int i= findPivot();
if (i < 0)returnnull;
for (int j= c[i]; i < n; c[i++]= ++j);
return c;
}
// read in N and k from command line, and print all subsets of size k from N elements
publicstaticvoid main(String[] args){
int N = Integer.parseInt(args[0]);
int S = Integer.parseInt(args[1]);
int k = Integer.parseInt(args[2]);
Combinations cc=new Combinations(N, S, k);
int innerCount = 1;
while (cc.hasMoreElements()){
int[] c= (int[])cc.nextElement();
System.out.print(innerCount+". ");
for (int i= 0; i < c.length; i++)
System.out.print(c[i]+" ");
System.out.println();
innerCount++;
}
}
}
% java Combinations 0 9 3
1. 0 1 2
2. 0 1 3
3. 0 1 4
4. 0 1 5
5. 0 1 6
6. 0 1 7
7. 0 1 8
8. 0 1 9
9. 0 2 3
10. 0 2 4
11. 0 2 5
12. 0 2 6
13. 0 2 7
14. 0 2 8
15. 0 2 9
16. 0 3 4
... till 120. 7 8 9
I tried to tweak the above code but to no avail. Is it possible to modify the above code to also print out numbers such as 011, 022 but not 110 or 101 (meaning with 2 same numbers but do not repeat each other again.) and to also avoid triple numbers such as 000, 111, 222, 333.....999?
By the way, is the above code thread-safe to be used in a web-environment if I put it in a bean and to be called from a JSP?
[4508 byte] By [
dufera] at [2007-11-26 13:54:15]
# 1
Hi,
try this class Combinator; it exposes public static methods to obtain combinations of objects. I hope this will help you.
Filippo
package com.dmd.math;
import java.util.* ;
public class Combinator {
private 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;
}
/*Il seguente metodo restituisce un oggetto List i cui elementi sono, a loro volta oggetti List. Ciascun elemento rappresenta una
combinazione degli oggetti objs in classe k . Il metodo e' private e static.*/
private static List getCombinations(Object[] objs,int k){
ArrayList result=new ArrayList();//Creo un'istanza ad un oggetto ArrayList vuota, e lo attribuisco alla variabile result.
if((objs.length!=0)&& (k!=0)&&(k<=objs.length)){//Verifico che i parametri rispettino i requisiti necessari per restituire un valore
for(int i=0;i<objs.length;i++){ //Ciclo con cui mi muovo all'inerno del vettore degli oggetti da combinare
Object currentObj=objs; //Ottengo l'oggetto i-esimo
Object[] othersObjs=new Object[objs.length-1];//Istanzio e dimensiono un array di (objs.length-1) oggetti con cui devo combinare l'i-esimo oggetto; tutti gli altri eccetto l'i-esimo
int z=0;
for(int j=0;j<objs.length;j++){//Ciclo di popolamento di othersObjs
if(!objs.equals(objs[j])){othersObjs[z]=objs[j];z++;} //verifico che l'oggetto che sto considerando non sia l'i-esimo che devo escludere, e se non lo e' lo inserisco nell'array che sto popolando
}
List othersList=getCombinations(othersObjs,k-1); //Effettuo la recursion, chiamdando il metodo corrente per l'insieme di oggetti eccetto l'i-esimo ed in classe k-1
Iterator othersListIter=othersList.iterator();//Ottengo l'oggetto Iterator per muovermi all'interno degli elementi di othersList
if(othersList.size()>0){ //Verifico che la lista non sia vuota
while(othersListIter.hasNext()){ //Ciclo di scansione degli elementi di othersList
List currentComb=(ArrayList)othersListIter.next();//Ottengo la lista di oggetti relativi ad una singola combinazione
currentComb.add(objs); //Aggiungo alla combinazione l'oggetto mancante ossia l'i-esimo
if(!containsCombination(result,currentComb)){result.add(currentComb); //verifico che la combinazione appena composta non sia gia' nelle combinazioni
//sin qui costruite. Se non c'e' la ggiungo.
}
}
}else{ // se la lista othersList e' vuota significa che uno dei parametri della recursione non e' valido ovvero significa che:
// o che ho passato un array vuoto, ovvero che sono arrivato al momento in cui devo inserire il primo oggetto
//o che k=0 ovvero ache, anche in questo caso sono arrivato al momento in cui devo inserire il primo oggetto
ArrayList myList=new ArrayList();// creo un'array List vuota
myList.add(objs); //aggiungo il mio oggetto
if(!containsCombination(result,myList)){result.add(myList);}}// inserisco la combinazione se non c'e' gia'
}
return result;
}else{return result; }
}
/*Il seguente metodo restituisce true se la combinazione combination e' contentuta nella lista di combinazioni container*/
private static boolean containsCombination(List container,List combination){
boolean result=false;// Inizialzzo il risultato a false
List comb=combination;//Valorizzo la variabile comb
Iterator containerIter =container.iterator();//Istanzio un oggetto Iterator per muovermi all'interno della lista di combinazioni container
while(containerIter.hasNext()){ //ciclo con cui mi muovo tra gli elementi di container
List combCheck=(List)containerIter.next(); //Ottengo la combinazione corrente combCheck
if(isSameCombination(combCheck,comb)){ return true;}//Verifico che la combinazione corrente sia uguale alla combinazione che sto verificando
//e se lo e' restituisco true
}
return result;
}
/*il seguente metodo restituisce true se la combinazione list e' identica a otherList*/
private static boolean isSameCombination(List list,List otherList){
boolean result=true;
Iterator iterOther;
iterOther=otherList.iterator();
while(iterOther.hasNext()){
Object currentObj=iterOther.next();//Ottengo l'oggetto corrente di otherList
if((list.size()==otherList.size())&& (!list.contains(currentObj))){//verifico se l'oggetto
return false;
}
}
return result;
}
/*Il seguente metodo resituisce un array di array rappresentato dalle combinazioni degli oggetti passati come
parametro objs in classe k .L'array restituito quindi avra' dimensioni [n!/(k!*(n-k)!)][k], dove n=numerosit?di objs ovvero objs.length
Il metodo e' statico.Il metodo restituisce null se i parametri sono errati ovvero:
Se objs.length<k
se n=0
se k=0
*/
public static Object[][] getArrayOfCombinations(Object[]objs,int k){
Object[][] result=null;//Inizializzo a null la variabile Object[][] restituita
List combList=getCombinations(objs,k); // Ottengo l'oggetto List combList; ciascun elemento di combList ?a sua volta un oggetto List
//i cui elementi sono gli oggetti relativi ad una singola combinazione
if(!combList.isEmpty()){//verifico che la lista non sia vuota; la lista e' vuota se i parametri objs e k non soddisfano le condizioni
//descritte in precedenza.
int combNumber=combList.size(); //Valorizzo il numero di combinazioni, mediante la dimensione di cmbList
result=new Object[combNumber][k];//Istanzio l'oggetto Object[][]result, determinandone le dimensioni dell'array
// Inizio a riempire il mio array result
int i=0;
Iterator combListIter=combList.iterator(); //Creo un'istanza Iterator di combList.
//Ottengo lo strumento per muovermi tra gli elementi di combList.
while(combListIter.hasNext()){ //Ciclo di scansione degli elementi di combList, che non sono altro che altri oggetti List contenenti gli oggetti combinati
List comb=(List)combListIter.next();//Ottengo un istanza ad un elemetgo List di combList, ovvero ad una specifica combinazione
int j=0;
Iterator combIter=comb.iterator(); //Creo un'istanza Iterator per muovemi all'interno della combinazione comb specifica
while(combIter.hasNext()){//Ciclo di scansione degli elementi di comb, che non sono altro che gli oggetti relativi alla combinazione specifica comb
result[j]=combIter.next();//Valorizzo l'elemento [j] dell'oggetto result, che non e' altro che l'oggetto alla j-esima posizione
//dell'i-esima combinazione
j++;
}
i++;
}
}
return result;//riempito l'array lo restituisco
}
private static List getDispositions(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=getDispositions(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);
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; }
}
public static Object[][] getArrayOfDispositions(Object[]objs,int k){
Object[][] result=null;
List combList=getDispositions(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;
}
public static Object[][] getArrayOfPermutations(Object[] objs){
return getArrayOfDispositions(objs,objs.length);
}
}
