Застрял с проблемой комбинации - PullRequest
Новая
       27

Застрял с проблемой комбинации

0 голосов
/ 15 марта 2011

У меня проблема с моей программой.Я извлек набор данных, и я хотел бы проверить, есть ли комбинация для определенного числа.Например, у меня есть массив int, 1 2 3 4 5, я хотел бы знать, есть ли комбинация для 7, может быть, и она должна ответить да, есть 3 + 4.

Я разобралсячто мне нужно использовать формулу комбинации.Поэтому я подумал, что внешний цикл может выглядеть как 5C1..5C2..5C3..etc, начиная с «take 1», затем «take 2» одновременно, чтобы выяснить все возможные комбинации.Проблема в том, что я застрял в том, как реализовать это в реальных кодах.

Я не очень хорошо разбираюсь в математике, определенная структура цикла действительно помогла бы.

Заранее большое спасибо!

Ответы [ 3 ]

2 голосов
/ 15 марта 2011

Вот метод, который получает все возможные суммы из списка целых чисел: 

public static void getAllPermutations(final List<Integer> data,
    final Set<Integer> holder){

    if(data.isEmpty()){
        return;
    }
    final Integer first = data.get(0);
    if(data.size() > 1){
        getAllPermutations(data.subList(1, data.size()), holder);
        for(final Integer item : new ArrayList<Integer>(holder)){
            holder.add(first.intValue() + item.intValue());
        }
    }
    holder.add(first);
}

Использование: 

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6);
Set<Integer> permutations = new TreeSet<Integer>();
getAllPermutations(data, permutations);
System.out.println(permutations);

Выход:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]

Хотя это решение не даст вам операндов, которые приводят к сумме, оно будет включать в себя что-нибудь от 1 до 1 + 2 + 3 + 4 + 5 + 6

1 голос
/ 15 марта 2011

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

bool findNode( int[] C , int givenNumber) {
 // compute the total sum
 int n = C.Length;
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 return T[givenNumber];
}

Это O (n * Sum).на самом деле достаточно проверить до O(n*given_number).

0 голосов
/ 15 марта 2011

Быстрое и грязное решение может состоять в создании 2D-массива, индекс которого (в обоих измерениях) - это позиция числа в массиве, а значения - это комбинации. Примерно так: 

//int i[] = { 1, 3, 5}, operation is 'add'
//you have a 3x3 array here:
//\ |1 3 5    <- the original values at their corresponding indices for quick reference, the array is the bottom right 3x3 matrix
//--+------
//1 |2 4 6    
//3 |4 6 8
//5 |6 8 10

int[][] a = new int[3][3];
//in a loop fill the array

Если вы хотите найти комбинации для 6, вы можете проверить все значения и получить индексы x и y для значений, равных 6. (В примере: 0/2, 1/1 и 2/0 ). Затем найдите номера этих индексов в исходном массиве (например, 0/2 -> 1 и 5, 1/1 -> 3 и 3, 2/0 -> 5 и 1).

Обратите внимание, что это быстрый и довольно несовершенный способ (особенно для больших массивов), который может возвращать больше перестановок, чем вам нужно или нужно (0/2 и 2/0 одинаковы для операции add). Однако это должно работать для многих возможных операций, например, x y будет другим для x = 1, y = 5 (результат: 1) и x = 5, y = 1 (результат: 5).

...