求一个排列组合的算法，我想了好久没想出来。。

1 0

求一个排列组合的算法，我想了好久没想出来。。10

输入数据是这样这的，有N组数字（N不确定），每组中数字的个数也不确定。
例如
A (1,2,3,4,5)
B(2,3,4,5,6)
C(9,0,9,9,0,6,5)
D(5,6,3,6,8)
......

要求是从每组数字中取出一个数字，然后相乘。所有乘起来的结果再相加。
例如，从A中取出1，B中取出2，C中取出5，D中取出5， 1*2*5*5=50
然后从A中取出1，B中取出2，C中取出5，D中取出8 ，1*2*5*8=80
.。。。。。
然后全部加起来。

其实乘积这些都不重要，关键是，需要相乘得那几个数字怎么获取到组合。
目前有想法是用多叉树去做。不过实现不太会写，求源码。最好是java的

数据结构算法组合

2012年12月24日 14:19

myidd00701
22
0 0 3

4个答案按时间排序按投票排序

1 0

取数的过程就是求这些集合的笛卡尔积吧。

google的guava库里的Sets有现成的求笛卡尔积方法（Sets.cartesianProduct) ，参考 http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/index.html

你有兴趣可以把源码下载下来看看是怎么实现的。不过由于你题目里某些组有重复数字，不能直接用这些数字组成Set，而应该先用下标值来算，比如
A (0,1,2,3,4)
B (0,1,2,3,4)
C (0,1,2,3,4,5,6)
D (0,1,2,3,4)
...
求出一个组合后再通过下标来取数。

2012年12月24日 20:03

kidneyball
205
0 1 13

1条评论

0 0

不想直接用集合的话，就只能用下标来算了。给你写个简单的迭代器吧

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 一个用于获取多个数组下标的笛卡尔积的迭代器。构造此迭代器时，指定各个数组的下标上限。
 * 此迭代器每次迭代将获取这些数组下标的笛卡尔积集合中的下一个元素
 *
 * @author Daniel
 *         Date: 25/12/12
 *         Time: 9:25 PM
 */
public class IndexCartesianProductIterator implements Iterator<int[]>
{
	private int[] elementSizes;
	private int[] next;
	private boolean calculated;
	private boolean hasNext;

	final int length;
	int tail;

	/**
	 * 构造一个{@link IndexCartesianProductIterator}实例
	 *
	 * @param elementSizes 待求笛卡尔积的各个数组的下标上限
	 */
	public IndexCartesianProductIterator(int... elementSizes)
	{
		this.elementSizes = elementSizes;
		length = elementSizes.length;
		next = new int[length];
		Arrays.fill(next, -1);
		calculated = false;
		tail = 0;
	}

	@Override
	public boolean hasNext()
	{
		if (calculated) return hasNext;
		calculated = true;
		hasNext = findNext();
		return hasNext;
	}

	@Override
	public int[] next()
	{
		if (calculated)
		{
			if (hasNext)
			{
				calculated = false;
				return next;
			} else throw new NoSuchElementException();
		} else
		{
			hasNext = findNext();
			if (hasNext) return next;
			else throw new NoSuchElementException();
		}
	}

	/**
	 * 计算下一个笛卡尔积元素，存放在next数组中。若该元素存在则返回true，否则返回false
	 *
	 * @return 若存在下一个笛卡尔积元素，则返回ture，否则返回false
	 */
	protected boolean findNext()
	{
		for(;;) {
			next[tail]++;
			if (next[tail] >= elementSizes[tail]) {
				tail--;
				if (tail < 0) return false;
			}
			else if (tail < length - 1) next[++tail] = -1;
			else return true;
		}
	}

	@Override
	public void remove()
	{
		throw new UnsupportedOperationException();
	}

	public static void main(String[] args)
	{
		for (IndexCartesianProductIterator it = new IndexCartesianProductIterator(3, 2, 4); it.hasNext(); )
		{
			System.out.println(Arrays.toString(it.next()));
		}
	}
}

其中的main方法是简单的测试代码，你可以去掉。

2012年12月25日 19:21

kidneyball
205
0 1 13