как подсчитать количество неупорядоченных разделов числа

Question

Я действительно застрял в этой проблеме.

В этой задаче вам предоставляется плата 2xN. Вам необходимо заполнить неотрицательных чисел в этой плате таким образом, что:

1. Сумма всех чисел, заполненных = N
2. Каждый из 2-х строк состоят из чисел в невозрастающие порядок
3. Каждый из столбцов N состоит из цифр в неуклонном порядке.

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

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

Пример:

вход-> 5

output-> 16

Answer 1

Из вашего примера (вход = 5, выход = 16) Я полагаю, только целые числа не допускаются.

Один наивное решение (перебор) является использование алгоритма обратной трассировки:

http://en.wikipedia.org/wiki/Backtracking

На этом сайте вы можете увидеть пример с судок доской заполняются до тех пор не будет найдено решение.

==

Например:

У вас есть массив целых чисел с размером 2N.

For position 0 you take first free number. 
If solution is not broken yet you go to position 1 of array. 
If solution is broken - stop as cannot back anymore 

    For position 1 you take next free number. 
    If solution is not broken you you go to position 2 of array. 
    If solution is broken you back to previous sten and take next free number. 

    For position 2... 

Обычно это делается с рекурсией. Я думаю, что на каждой позиции (уровень рекурсии) числа могут быть взяты из пула 0..N.

Попробуйте - удачи.

EDIT:

Здесь правильное решение (с использованием обратного прослеживания Algo):

private final int N = 5; 

// 2 rows in one array [0..N-1, N..2N-1] 
private int[] board = new int[2 * N]; 

// found solution counter 
int found = 0; 

/* 
* this method set next number to current position 
* and recursively go to next position. 
*/ 
public void check(int position) { 

    // if board is complete - check if valid 
    if (position == 2 * N) { 
     if (isValid()) { 
      System.out.println("foun : " + Arrays.toString(board)); 
      found++; 
     } 
     return; 
    } 


    // if board is not complete - put all numbers (0..N) into current position 
    // and recursively go to next position 
    for (int v = 0; v <= N; v++) { 
     board[position] = v; 

     // if solution is already broken - step backwards 
     // see: backtracking algorithms 
     if (isBroken(position)) { 
      return; 
     } 

     check(position + 1); 
    } 
} 

public boolean isValid() { 

    // condition 1 
    int sum = 0; 
    for (int i = 0; i < board.length; i++) { 
     sum += board[i]; 
    } 
    if (sum != N) { 
     return false; 
    } 

    // conditin 2 
    int prev = board[0]; 
    for (int i = 1; i < N; i++) { 
     if (board[i] > prev) { 
      return false; 
     } 
     prev = board[i]; 
    } 
    prev = board[N]; 
    for (int i = N + 1; i < 2 * N; i++) { 
     if (board[i] > prev) { 
      return false; 
     } 
     prev = board[i]; 
    } 

    // condition 3 
    for (int i = 0; i < N; i++) { 
     int top = board[i]; 
     int bottom = board[i + N]; 
     if (top < bottom) { 
      return false; 
     } 
    } 

    // valid 
    return true; 
} 

// simplified version of this method - but correct 
public boolean isBroken(int current) { 
    int sum = 0; 
    for (int i = 0; i <= current; i++) { 
     sum += board[i]; 
    } 
    return sum > N; 
} 

public void start() { 
    check(0); 
    System.out.println("found: " + found); 
} 

И программа выхода для N = 5:

found : [1, 1, 1, 0, 0, 1, 1, 0, 0, 0] 
found : [1, 1, 1, 1, 0, 1, 0, 0, 0, 0] 
found : [1, 1, 1, 1, 1, 0, 0, 0, 0, 0] 
found : [2, 1, 0, 0, 0, 1, 1, 0, 0, 0] 
found : [2, 1, 0, 0, 0, 2, 0, 0, 0, 0] 
found : [2, 1, 1, 0, 0, 1, 0, 0, 0, 0] 
found : [2, 1, 1, 1, 0, 0, 0, 0, 0, 0] 
found : [2, 2, 0, 0, 0, 1, 0, 0, 0, 0] 
found : [2, 2, 1, 0, 0, 0, 0, 0, 0, 0] 
found : [3, 0, 0, 0, 0, 2, 0, 0, 0, 0] 
found : [3, 1, 0, 0, 0, 1, 0, 0, 0, 0] 
found : [3, 1, 1, 0, 0, 0, 0, 0, 0, 0] 
found : [3, 2, 0, 0, 0, 0, 0, 0, 0, 0] 
found : [4, 0, 0, 0, 0, 1, 0, 0, 0, 0] 
found : [4, 1, 0, 0, 0, 0, 0, 0, 0, 0] 
found : [5, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
found: 16 

Answer 2

Вот перебором путь: так как это 2xN-матрица, а сумма всех чисел должна быть N, самым простым решением является заполнение первой строки 1, а вторая строка - 0. Теперь вам понадобится рекурсивный алгоритм, который берет действительную доску и удаляет 1 из любой «свободной» позиции и добавляет ее в любое юридическое положение. Эта доска также является решением.Под «свободным» я подразумеваю число n в позиции [i, j], где [i + 1, j] < = n - 1 и [i, j + 1] < = n - 1. Затем вы рекурсивно вызываете алгоритм на новые платы, и сохранить все.

Все, что осталось - это дедупликация решений.

Пример алгоритма на входе 5: Начальное решение:

11111 
00000 

Единственный "свободный" номер [0, 4]. Удалите 1, единственные юридические позиции - [0, 0] и [0, 1]. Это дает Вам 2 новые решения

21110 
00000 

и

11110 
10000 

Теперь применим тот же алгоритм снова на обоих этих решений. Обратите внимание, что на 2-й доске теперь есть 2 «свободных» номера. Повторяйте, пока не дойдете до

50000 
00000 

EDIT: Просто было очень весело кодирование этого примера. Не проверить это, но вот где моя голова идет:

public void TwoRowBoard() 
{ 
    var board = new int[2, N]; 
    //Create initial, simplest solution. 
    for (int i = 0; i < N; i++) 
    { 
     board[0, i] = 1; 
    } 

    var solutions = new List<int[,]>(); 
    RecursiveSolve(board, solutions); 
} 

private void RecursiveSolve(int[,] board, List<int[,]> solutions) 
{ 
    var freeNumbers = GetFreeNumbers(board); 
    foreach (var freeNumber in freeNumbers) 
    { 
     board[freeNumber.i, freeNumber.j] -= 1; 
     var legalPositions = GetLegalPositions(board); 

     foreach (var legalPosition in legalPositions) 
     { 
      var newBoard = Copy(board); 
      newBoard[legalPosition.i, legalPosition.j] += 1; 
      solutions.Add(newBoard); 
      RecursiveSolve(newBoard, solutions); 
     } 
    } 
} 

private List<Coordinates> GetLegalPositions(int[,] board) 
{ 
    //Position 0, 0 is always legal. 
    var results = new List<Coordinates> {new Coordinates {i = 0, j = 0}}; 

    //Row 0 
    for (int j = 1; j < N; j++) 
    { 
     if (board[0, j - 1] > board[0, j]) 
     { 
      results.Add(new Coordinates{i = 0, j = j}); 
     } 
    } 

    //Row 1. Board[1, higher than N/2] are never legal positions. 
    for (int j = 0; j <= N /2; j++) 
    { 
     if (board[1, j - 1] > board[1, j] 
      && board[0, j] > board[1, j]) 
     { 
      results.Add(new Coordinates{i = 1, j = j}); 
     } 
    } 

    return results; 
} 


private List<Coordinates> GetFreeNumbers(int[,] board) 
{ 
    var results = new List<Coordinates>(); 
    for (int i = 0; i < 2; i++) 
    { 
     for (int j = 0; j < N; j++) 
     { 
      if (i == 0 && j == 0) 
      { 
       continue; 
      } 
      if (i == 0) 
      { 
       if (j == N - 1 && board[0, j] > 0) 
       { 
        results.Add(new Coordinates {i = 0, j = j}); 
       } 
       else if (board[0, j] > board[1, j] 
         && board[0, j] > board[0, j + 1]) 
       { 
        results.Add(new Coordinates {i = 0, j = j}); 
       } 
      } 
      else 
      { 
       if (j > N/2 && board[1, j] > 0) 
       { 
        throw new Exception("Don't see how it's possible for board[1, N/2 or higher] to not be 0"); 
       } 
       if (board[1, j] > board[1, j + 1]) 
       { 
        results.Add(new Coordinates{i = 1, j = j}); 
       } 
      } 
     } 
    } 
    return results; 
} 

public class Coordinates 
{ 
    public int i { get; set; } 
    public int j { get; set; } 
} 

Answer 3

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

Итак, предположим, что вы знаете решение для N. Вы хотите N + 1. Итак, что вам нужно сделать, это взять все решения для N и посмотреть, где вы можете вставить дополнительный 1 там, не нарушая никаких ограничений. То есть супер накладывает решение N на плату N + 1, затем попробуйте во всех 2N местах добавить 1 без ограничений на разрыв. Затем сохраните их все в наборе, чтобы они были дедуплированы.

В любом случае, похожее на http://en.wikipedia.org/wiki/Partition_(number_theory)