我应该如何优化以下生成器中的
算法中存在问题的特定区域是整个
该算法的背景是很难找到。例如，在Knuth 7.2.1.3中，他仅表示可以完成这项工作（并提供了一个练习来证明算法是可能的），但没有给出算法。同样，我拥有半打关于组合数学的高级文本（包括Papadimitriou和Kreher/Stimson），但其中没有一个提供了生成多重集合组合的算法。Kreher将其留给“读者作为练习”。无论如何，如果您可以改进上述算法或提供比我的实现更有效的工作实现的参考，请告诉我。请仅提供迭代算法（请勿使用递归）。
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