algorithm - 我需要帮助来创建一个算法以从数字列表中返回可能的数字组列表

Question

我需要开发的搜索算法的一部分包括一个函数，该函数接收一个整数列表并根据某些规则返回一个整数列表列表，这里是规范。

输入列表可以有任意数量的数字，不同于最小和最大预定值。该函数需要返回输入数字的所有可能组合，这些组合是连续的并且大小为 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] ]

技巧部分是输入列表可以接收任意数量的 clown 字符。这些 clown 可以采用最小值和最大值内的任何值。

使用 clown 的例子:

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] 
]

当在输入中处理任何可能数量的 clown 时，我无法想出任何可以解决此问题的算法。

你有什么建议或伪代码可以分享来帮助我解决这个问题吗？

Answer 1

这是一个可能需要根据您的需要进行调整的递归。这个想法是从每个可能的起点枚举到每个可能的终点。 clown 仅用于不在列表中的数字。由于列表可能是稀疏的，一种方法是将每个数字视为图中的一个节点，在仍然看不见的起点上执行搜索。

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);