java - How can I improve my algorithm for generating combinations of a multiset? -

how can optimize next() , hasnext() methods in following generator produces combinations of bounded multiset? (i posted c++ java because code c++-compatible , has no java-specific elements not convert directly c++.

the specific areas of algorithm problematic entire hasnext() method may unnecessarily complicated, , line:

if( current[xslot] > 0 ) aiitemsused[current[xslot]]--;

which has if-statement think removed somehow. had earlier version of algorithm had of backtracking before return statement , consequently had simpler hasnext() test, not version work.

the background of algorithm is difficult find. example, in knuth 7.2.1.3 merely says can done (and gives exercise prove algorithm possible), not give algorithm. likewise, have half dozen advanced texts on combinatorics (including papadimitriou , kreher/stimson) , none of them give algorithm generating combinations of multiset. kreher leaves "exercise reader". anyway, if can improve algorithm above or provide reference working implementation more efficient mine appreciate it. please give iterative algorithms (no recursion, please).

/** iterator returns 1-based array of integers. when last combination reached hasnext() false.   * @param aiitems one-based array containing number of items available each unique item type aiitems[0] number of item types   * @param ctslots  number of slots items go   * @return iterator generates 1-based array containing combinations or null in event of error.   */ public static java.util.iterator<int[]> combination( final int[] aiitems, final int ctslots ){ // multiset combination limited number of slots     combinatoriciterator<int[]> iterator = new combinatoriciterator<int[]>(){         int xslot;         int xitemtype;         int ctitemtype;         int[] current = new int[ctslots + 1];         int[] aiitemsused = new int[aiitems[0] + 1];         { reset(); current[0] = ctslots; ctitemtype = aiitems[0]; }         public boolean hasnext(){             int xuseslot = ctslots;             int icurrenttype = ctitemtype;             int ctitemsused = 0;             int cttotalitemsused = 0;             while( true ){                 int xusedtype = current[xuseslot];                 if( xusedtype != icurrenttype ) return true;                 ctitemsused++;                 cttotalitemsused++;                 if( cttotalitemsused == ctslots ) return false;                 if( ctitemsused == aiitems[xusedtype] ){                     icurrenttype--;                     ctitemsused = 0;                 }                 xuseslot--;             }         }         public int[] next(){             while( true ){                 while( xitemtype == ctitemtype ){                     xslot--;                     xitemtype = current[xslot];                 }                 xitemtype++;                 while( true ){                     while( aiitemsused[xitemtype] == aiitems[xitemtype] && xitemtype != current[xslot] ){                         while( xitemtype == ctitemtype ){                             xslot--;                             xitemtype = current[xslot];                         }                         xitemtype++;                     }                     if( current[xslot] > 0 ) aiitemsused[current[xslot]]--;                     current[xslot] = xitemtype;                     aiitemsused[xitemtype]++;                     if( xslot == ctslots ){                         return current;                     }                     xslot++;                 }             }          }         public int[] get(){ return current; }         public void remove(){}         public void set( int[] current ){ this.current = current; }         public void setvalues( int[] current ){             if( this.current == null || this.current.length != current.length ) this.current = new int[current.length];             system.arraycopy( current, 0, this.current, 0, current.length );         }         public void reset(){             xslot = 1;             xitemtype = 0;             arrays.fill( current, 0 ); current[0] = ctslots;             arrays.fill( aiitemsused, 0 ); aiitemsused[0] = aiitems[0];         }     };     return iterator; } 

additional info

some of respondents far seem not understand difference between set , bounded multiset. bounded multiset has repeating elements. example { a, a, b, b, b, c } bounded multiset, encoded { 3, 2, 3, 1 } in algorithm. note leading "3" number of item types (unique items) in set. if supply algorithm, following test should produce output shown below.

    private static void combination_multiset_test(){         int[] aiitems = { 4, 3, 2, 1, 1 };         int islots = 4;         java.util.iterator<int[]> iterator = combination( aiitems, islots );         if( iterator == null ){             system.out.println( "null" );             system.exit( -1 );         }         int xcombination = 0;         while( iterator.hasnext() ){             xcombination++;             int[] combination = iterator.next();             if( combination == null ){                 system.out.println( "improper termination, no result" );                 system.exit( -1 );             }             system.out.println( xcombination + ": " + arrays.tostring( combination ) );         }         system.out.println( "complete" );     }   1: [4, 1, 1, 1, 2] 2: [4, 1, 1, 1, 3] 3: [4, 1, 1, 1, 4] 4: [4, 1, 1, 2, 2] 5: [4, 1, 1, 2, 3] 6: [4, 1, 1, 2, 4] 7: [4, 1, 1, 3, 4] 8: [4, 1, 2, 2, 3] 9: [4, 1, 2, 2, 4] 10: [4, 1, 2, 3, 4] 11: [4, 2, 2, 3, 4] complete 

edit: done adjusting answer according clarified question

main idea: again, resulting selection can encoded similar custom numeral system. 1 increment counter , interpret counter selection.

however, since there additional restriction of size of selection == target. naive way implement restriction check size of resulting selection , skip ones not satisfy restriction. slow.

so did little cleverer increment jump selection correct size directly.

sorry code in python. did in way comparable java iterator interface. input & output format is:

haves[i] := multiplicity of i-th item in collection target := output collection must have size 

the code:

class perm(object):     def __init__(self,items,haves,target):         assert sum(haves) >= target         assert all(h > 0 h in haves)         self.items = items         self.haves = haves         self.target = target         self.ans = none         self.stop = false     def __iter__(self):         return self     def reset(self):         self.ans = [0]*len(self.haves)         self.__fill(self.target)         self.stop = false     def __fill(self,n):         """fill ans lsb n bits"""         if n <= 0: return         = 0         while n > self.haves[i]:             assert self.ans[i] == 0             self.ans[i] = self.haves[i]             n -= self.haves[i]             += 1         assert self.ans[i] == 0         self.ans[i] = n     def __inc(self):         """increment lsb, carry when 'target' or 'haves' constrain broken"""         # in fact, 'target' constrain broken on left non-zero entry         # find left non-zero         = 0         while self.ans[i] == 0:             += 1         # set 0         l = self.ans[i]         self.ans[i] = 0         # increment answer, , carry         while true:             # increment next entry, if possible             += 1             if >= len(self.ans):                 self.stop = true                 raise stopiteration             #             if self.ans[i] == self.haves[i]:                 l += self.ans[i]                 self.ans[i] = 0             else:                 l -= 1                 self.ans[i] += 1                 break         return l     def next(self):         if self.stop:             raise stopiteration         elif self.ans none:             self.reset()         else:             l = self.__inc()             self.__fill(l)         return self.ans 

note items argument isn't used.

the assert in __init__ make clear of assumption input.

the assert in __fill show convenient property of self.ans in context __fill called.

here nice skeleton testing code:

test_cases = [([3,2,1], 3),               ([3,2,1], 5),               ([3,2,1], 6),               ([4,3,2,1,1], 4),               ([1,3,1,2,4], 4),              ]  p = perm(none,*test_cases[-1]) p in p:     print p     #raw_input() 

example result input ([1,3,1,2,4], 4):

[1, 3, 0, 0, 0] [1, 2, 1, 0, 0] [0, 3, 1, 0, 0] [1, 2, 0, 1, 0] [0, 3, 0, 1, 0] [1, 1, 1, 1, 0] [0, 2, 1, 1, 0] [1, 1, 0, 2, 0] [0, 2, 0, 2, 0] [1, 0, 1, 2, 0] [0, 1, 1, 2, 0] [1, 2, 0, 0, 1] [0, 3, 0, 0, 1] [1, 1, 1, 0, 1] [0, 2, 1, 0, 1] [1, 1, 0, 1, 1] [0, 2, 0, 1, 1] [1, 0, 1, 1, 1] [0, 1, 1, 1, 1] [1, 0, 0, 2, 1] [0, 1, 0, 2, 1] [0, 0, 1, 2, 1] [1, 1, 0, 0, 2] [0, 2, 0, 0, 2] [1, 0, 1, 0, 2] [0, 1, 1, 0, 2] [1, 0, 0, 1, 2] [0, 1, 0, 1, 2] [0, 0, 1, 1, 2] [0, 0, 0, 2, 2] [1, 0, 0, 0, 3] [0, 1, 0, 0, 3] [0, 0, 1, 0, 3] [0, 0, 0, 1, 3] [0, 0, 0, 0, 4] 

performance each next() call takes o(h) h number of types of items (size of haves list).