Получение всех возможных сумм, которые складываются в данное число

Question

Я делаю математическое приложение для Android.В одном из этих полей пользователь может ввести int (без цифр и выше 0).Идея состоит в том, чтобы получить все возможные суммы, которые составляют это int, без двойных чисел (4 + 1 == 1 + 4 в этом случае).Известно только одно int.

Например:

Скажите, что пользователь вводит 4, я хотел бы, чтобы приложение вернуло:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Очевидно4 == 4, так что это тоже должно быть добавлено.Любые предложения относительно того, как я должен сделать это?

Answer 1

Вот простой алгоритм, который предназначен для этого

из: 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);
    }

}

Answer 2

Существуют короткие и элегантные рекурсивные решения для их генерации, но следующее может быть проще в использовании и внедрении в существующий код:

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]

Answer 3

Это математическая концепция, известная как partitions .В общем, это ... сложно, но есть приемы для небольших чисел.Множество полезных вещей со ссылкой на вики-страницу.

Answer 4

Это связано с алгоритмом проблема подмножества сумм .

N = {N * 1, (N-1) +1, (N-2) +2, (N-3) +3 .., N-1 = {(N-1), ((N-1) -1) +2, ((N-1) -1) +3 ..}

и т.д..

Так что это рекурсивная функция, включающая подстановку; однако имеет ли это смысл при работе с большими числами, это то, что вам придется решать самостоятельно.

Answer 5

Для числа N вы знаете, что максимальное число терминов равно N., поэтому вы начнете перечислять все эти возможности.

Для каждого возможного количества терминов существует ряд возможностей.Формула ускользает от меня сейчас, но в основном идея состоит в том, чтобы начать с (N + 1-i + 1 + ... + 1), где i - количество слагаемых, и переместить 1 с слева направо, второй случай будетбыть (Ni + 2 + ... + 1) до тех пор, пока вы не сможете сделать еще один ход, не приведя к несортированной комбинации.

(Кроме того, почему вы снова пометили этот андроид?)

Answer 6

Все эти решения кажутся немного сложными. Это может быть достигнуто простым «увеличением» списка, инициализированного, чтобы содержать 1 = N.

Если люди не возражают против преобразования из c ++, следующий алгоритм выдает необходимый вывод.

bool next(vector<unsigned>& counts) {
    if(counts.size() == 1)
        return false;

    //increment one before the back
    ++counts[counts.size() - 2];

    //spread the back into all ones
    if(counts.back() == 1)
        counts.pop_back();
    else {
        //reset this to 1's
        unsigned ones = counts.back() - 1;
        counts.pop_back();
        counts.resize(counts.size() + ones, 1);
    }
    return true;
}

void print_list(vector<unsigned>& list) {
    cout << "[";
    for(unsigned i = 0; i < list.size(); ++i) {
        cout << list[i];
        if(i < list.size() - 1)
            cout << ", ";
    }
    cout << "]\n";
}

int main() {
    unsigned N = 5;
    vector<unsigned> counts(N, 1);
    do {
        print_list(counts);
    } while(next(counts));
    return 0;
}

для N = 5 алгоритм дает следующее

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]