如何优化以下生成有界多重集组合的生成器中的next()和方法？hasNext()（我将其发布到 C++ 和 Java 上，因为代码与 C++ 兼容，并且没有不直接转换为 C++ 的 Java 特定元素。
有问题的算法的特定区域是整个hasNext()方法，可能不必要地复杂，并且行：
if( current[xSlot] > 0 ) aiItemsUsed[current[xSlot]]--;
它有一个我认为可以以某种方式删除的 if 语句。我有一个早期版本的算法，它在 return 语句之前有一些回溯，因此有一个更简单的hasNext()测试，但我无法让那个版本工作。
这个算法的背景是很难找到。例如，在 Knuth 7.2.1.3 中，他只是说可以做到（并给出了一个练习来证明该算法是可能的），但没有给出算法。同样，我有六本关于组合学的高级文本（包括 Papadimitriou 和 Kreher/Stimson），但没有一篇给出生成多集组合的算法。Kreher 将其作为“读者练习”。无论如何，如果您可以改进上述算法或提供比我更有效的工作实现的参考，我将不胜感激。请只给出迭代算法（请不要递归）。
/** The iterator returns a 1-based array of integers. When the last combination is reached hasNext() will be false.
* @param aiItems One-based array containing number of items available for each unique item type where aiItems[0] is the number of item types
* @param ctSlots The number of slots into which the items go
* @return The iterator which generates the 1-based array containing the combinations or null in the event of an error.
*/
public static java.util.Iterator<int[]> combination( final int[] aiItems, final int ctSlots ){ // multiset combination into a 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;
}
附加信息
到目前为止，一些受访者似乎不理解集合和有界多重集之间的区别。有界多重集具有重复元素。例如 { a, a, b, b, b, c } 是一个有界多重集，在我的算法中将被编码为 { 3, 2, 3, 1 }。请注意，前导“3”是集合中项目类型（唯一项目）的数量。如果您提供算法，则以下测试应产生如下所示的输出。
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