Мне нужна помощь в создании алгоритма для возврата списка возможных групп чисел из списка номеров - PullRequest
Новая
       15

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

1 голос
/ 27 мая 2019

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

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

Порядок групп выходных данных не важен.

Например: 

min = 1;
max = 10;

input = [1, 2, 3, 4, 6, 7, 8]

output = [ [1, 2, 3], [2, 3, 4], [1, 2, 3, 4], [6, 7, 8] ]

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

Пример использования джокеров: 

min = 1;
max = 10;

input = [1, 2, 3, 4, 6, 7, 8, J]

output = [ 
    [1, 2, 3], 
    [2, 3, 4], 
    [1, 2, 3, 4], 
    [6, 7, 8], 
    [1, 2, 3, 4, J, 6, 7, 8], 
    [2, 3, 4, J, 6, 7, 8], 
    [3, 4, J, 6, 7, 8],
    [4, J, 6, 7, 8], 
    [J, 6, 7, 8], 
    [6, 7, 8, J], 
    [7, 8, J],
    [1, 2, 3, 4, J, 6, 7], 
    [1, 2, 3, 4, J, 6], 
    [1, 2, 3, 4, J, 6], 
    [1, 2, 3, 4, J] 
]

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

Есть ли какие-либо предложения или псевдокод, которыми вы могли бы поделиться, чтобы помочь мне с этой проблемой?

1 Ответ

1 голос
/ 28 мая 2019

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

Код JavaScript: 

function f(A, jokerMin, jokerMax, globalMin, globalMax, minSeqLen){
  // Record available elements
  let sansJokers = A.filter(x => x != 'J');
  let numbers = new Set(sansJokers);
  let numJokers = A.length - sansJokers.length;
  let seen = new Set();
    
  // Given a starting point,
  // go as far as possible
  function g(js, n, comb){
    let result = comb.length >= minSeqLen ? [comb] : [];
    
    if (globalMin <= n && n <= globalMax){
      if (numbers.has(n)){
        return result.concat(
          g(js, n + 1, comb.slice().concat(n)));
          
      } else if (js && jokerMin <= n && n <= jokerMax){
        return result.concat(
          g(js - 1, n + 1, comb.slice().concat('J')));

      } else {
        return result;
      }
    
    } else {
      return result;
    }
  }
  
  let result = [];
  
  // Find starting points
  
  // If there are at least minSeqLen
  // jokers, we can start anywhere.
  // Otherwise, look only below
  // existing numbers since a pure
  // joker sequence will have to 
  // connect to a number to be valid
  if (numJokers >= minSeqLen){
    return ['Enough jokers to start anywhere'];
  
  } else {
    for (let n of numbers){
      // search lower
      let tempN = n - 1;
      
      while (!seen.has(tempN) &&
        !numbers.has(tempN) &&
        tempN >= globalMin &&
        tempN >= jokerMin){
        
        seen.add(tempN);
        result = result.concat(
          g(numJokers, tempN, []));
        tempN--;
      }
      
      seen.add(n);
      result = result.concat(
        g(numJokers, n, []));
    }
  }
  
  return result;
}

var jokerMin = 1;
var jokerMax = 10;
var globalMin = 1;
var globalMax = 15;
var minSeqLen = 3;

var input = [1, 2, 3, 4, 7, 8, 'J', 'J']

let str = '';

for (let comb of f(input, jokerMin, jokerMax, globalMin, globalMax, minSeqLen))
  str += JSON.stringify(comb) + '\n';

console.log(str);
...