私はアンドロイド用の数学アプリを作っています。これらのフィールドの 1 つで、ユーザーは int (数字なし、0 より大きい) を入力できます。アイデアは、この int を構成するすべての可能な合計を double なしで取得することです (この場合は 4+1 == 1+4)。知られている唯一のことは、この 1 つの int です。
例えば：
ユーザーが 4 を入力すると、アプリに次のように返してもらいたいとします。
明らかに 4 == 4 なので、それも追加する必要があります。これを行う方法について何か提案はありますか?
これは、それを行うことを目的とした単純なアルゴリズムです
から: http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html
public class Partition { public static void partition(int n) { partition(n, n, ""); } public static void partition(int n, int max, String prefix) { if (n == 0) { StdOut.println(prefix); return; } for (int i = Math.min(max, n); i >= 1; i--) { partition(n-i, i, prefix + " " + i); } } public static void main(String[] args) { int N = Integer.parseInt(args[0]); partition(N); } }
それらを生成するための短くて洗練された再帰的な解決策がありますが、次の方法を使用して既存のコードに実装する方が簡単な場合があります。
import java.util.*;
public class SumIterator implements Iterator<List<Integer>>, Iterable<List<Integer>> {
// keeps track of all sums that have been generated already
private Set<List<Integer>> generated;
// holds all sums that haven't been returned by `next()`
private Stack<List<Integer>> sums;
public SumIterator(int n) {
// first a sanity check...
if(n < 1) {
throw new RuntimeException("'n' must be >= 1");
}
generated = new HashSet<List<Integer>>();
sums = new Stack<List<Integer>>();
// create and add the "last" sum of size `n`: [1, 1, 1, ... , 1]
List<Integer> last = new ArrayList<Integer>();
for(int i = 0; i < n; i++) {
last.add(1);
}
add(last);
// add the first sum of size 1: [n]
add(Arrays.asList(n));
}
private void add(List<Integer> sum) {
if(generated.add(sum)) {
// only push the sum on the stack if it hasn't been generated before
sums.push(sum);
}
}
@Override
public boolean hasNext() {
return !sums.isEmpty();
}
@Override
public Iterator<List<Integer>> iterator() {
return this;
}
@Override
public List<Integer> next() {
List<Integer> sum = sums.pop(); // get the next sum from the stack
for(int i = sum.size() - 1; i >= 0; i--) { // loop from right to left
int n = sum.get(i); // get the i-th number
if(n > 1) { // if the i-th number is more than 1
for(int j = n-1; j > n/2; j--) { // if the i-th number is 10, loop from 9 to 5
List<Integer> copy = new ArrayList<Integer>(sum); // create a copy of the current sum
copy.remove(i); // remove the i-th number
copy.add(i, j); // insert `j` where the i-th number was
copy.add(i + 1, n-j); // insert `n-j` next to `j`
add(copy); // add this new sum to the stack
} //
break; // stop looping any further
}
}
return sum;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
次のように使用できます。
int n = 10;
for(List<Integer> sum : new SumIterator(n)) {
System.out.println(n + " = " + sum);
}
これは次のように出力されます:
10 = [10] 10 = [6, 4] 10 = [6, 3, 1] 10 = [6, 2, 1, 1] 10 = [7, 3] 10 = [7, 2, 1] 10 = [8, 2] 10 = [9, 1] 10 = [5, 4, 1] 10 = [5, 3, 1, 1] 10 = [5, 2, 1, 1, 1] 10 = [8, 1, 1] 10 = [7, 1, 1, 1] 10 = [4, 3, 1, 1, 1] 10 = [4, 2, 1, 1, 1, 1] 10 = [6, 1, 1, 1, 1] 10 = [5, 1, 1, 1, 1, 1] 10 = [3, 2, 1, 1, 1, 1, 1] 10 = [4, 1, 1, 1, 1, 1, 1] 10 = [3, 1, 1, 1, 1, 1, 1, 1] 10 = [2, 1, 1, 1, 1, 1, 1, 1, 1] 10 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
これは、パーティションとして知られる数学的概念です。一般的には… 難しいですが、少数の場合はテクニックがあります。wiki ページからリンクされた便利なものがたくさんあります。
数 N の場合、項の最大数は N であることがわかっているため、これらすべての可能性を列挙することから始めます。
項の可能な数ごとに、いくつかの可能性があります。式は今ではわかりませんが、基本的には (N+1-i + 1 + ... + 1) から始めます。i は項の数で、1 を左から右に移動します。 (Ni + 2 + ... + 1) は、ソートされていない組み合わせになることなく別の手を実行できなくなるまで続きます。
(また、なぜこのアンドロイドに再度タグを付けたのですか?)
これは、部分和問題アルゴリズムに関連しています。
N = {N*1, (N-1)+1, (N-2)+2, (N-3)+3 .., N-1 = {(N-1), ((N-1) -1)+2, ((N-1)-1)+3..}
等
したがって、これは置換を伴う再帰関数です。ただし、大きな数を扱うときにそれが意味をなすかどうかは、自分で決める必要があります。