继续整数数组的模式

Question

给定一个或多个等长整数数组的集合，我希望预测最有可能的下一个数组。元素通常只会递增 1 或跳回零，但其他更改绝对是可能的。

示例 1：

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
I'd expect to get:
[0, 0, 3]

示例 2：

[2, 0, 0]
[4, 1, 0]
[6, 2, 0]
I'd expect to get:
[8, 3, 0]

示例 3：

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
I'd expect to get:
[0, 2, 0]

案例 1 和案例 2 很容易发现，但我很难弄清楚如何检测示例 3 中的模式。我需要什么样的关键字 google在这里取得进展？

编辑：对保罗的回应。尽管模式中的每个元素可能看起来像任何东西，但如果模式不是通过不断添加和循环重置为零以某种方式建立起来的，那么该模式已经非常荒谬以至于我的算法不再需要做好工作。所以我不关心复杂的多项式或 [+1, +1, +2, -5, +7] 加法规则。

Answer 1

所以如果我做对了，在给定的输入中你有

常量（如例1，第1列）
常数加法（如例1第3列）
周期性（示例 3 第 3 列）

我猜认为两者中的任何一个，或者三个结合在一起都不会错（如示例3，第2列是常数和常数加法的组合）。

首先，我们必须考虑到对于任何给定的输入，我们必须考虑到所有情况都可能发生在一列上。您可以通过使用不同的变量为任何这些情况创建一个对象，一个结构，甚至 none 个。

其次，您必须检查每一列。因此，虽然尚未完全检查该列，但我们会寻找多项内容：

有常数吗？（两个连续的行具有相同的数字）。如果为真，我们会在变量中记住常量和最后一行。
两个连续的数字有区别吗？如果是，那么我们有常数加法，我们在变量中记住它在加法中使用的常数以及加法发生的位置。注意力！我们必须记住，加法可以发生在 3 个常数之后。所以如果我们有一个常量和常量加法，我们就得看看这个常量在什么地方停止了，这样我们才能在加法之后继续它。
有循环吗？第一个数字是否等于来自同一列但任何其他行的任何其他数字？如果发生这种情况，我们只需要记住在多少次加法（AND/OR常数）之后循环开始。这是最棘手的一个：我们可以有常量、常量加法和循环。但这也不难，因为之前我们有常数和常数加法。所以，一个循环就是这两个重复自己。

这是使用您提供给我们的信息寻找简单模式的算法。希望对你有用。

Answer 2

使用 Georgian 的基本思想，我放弃了在 20 行或更少的代码中完成此任务的尝试。下面的代码当然不能检测到所有模式，但对于我的目的来说已经足够了。

它将能够识别由重复数字或重复增量组成的模式：

尽管它无法检测二阶模式，例如： 0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,...

/// <summary>
/// Create a difference array. This array contains all the values that need to be added to 
/// the elements in the original array in order to yield the next element. 
/// The difference array will be one element shorter.
/// </summary>
/// <param name="array">Array to operate on.</param>
/// <returns>Difference array.</returns>
public static int[] ToDifferenceArray(this int[] array)
{
  if (array == null || array.Length == 0)
    throw new ArgumentNullException("array");
  if (array.Length == 1)
    return new int[0];

  int[] div = new int[array.Length - 1];
  for (int i = 0; i < array.Length - 1; i++)
    div[i] = array[i + 1] - array[i];

  return div;
}
/// <summary>
/// Determine whether an array of integers contains repeating elements.
/// the last iteration of the cycle may be incomplete.
/// </summary>
/// <param name="array">Array to examine.</param>
/// <returns>Length of cycle or 0 if no cycle could be found.</returns>
public static int FindCycle(this int[] array)
{
  return FindCycle(array, 0);
}
/// <summary>
/// Determine whether an array of integers contains repeating elements.
/// the last iteration of the cycle may be incomplete.
/// </summary>
/// <param name="array">Array to examine.</param>
/// <param name="start">Index for cycle search.</param>
/// <returns>Length of cycle or 0 if no cycle could be found.</returns>
public static int FindCycle(this int[] array, int start)
{
  if (array == null || array.Length == 0)
    throw new ArgumentNullException("array");
  if (start < 0)
    throw new IndexOutOfRangeException("Search start may not be a negative number.");
  if (start >= array.Length)
    throw new IndexOutOfRangeException("Search start may not be larger than or equal to the length of the array.");

  int index0 = start;
  int index1 = index0;
  while (true)
  {
    // Find next occurrence of pattern start value.
    index1 = array.FirstIndexOf(array[index0], index1 + 1);
    if (index1 < 0)
      return 0;

    // Length of potential cycle.
    int length = (index1 - index0);

    // Test each remaining element of the array to see 
    // whether it indeed repeats at regular intervals.
    bool validCycle = true;
    for (int i = index1 + 1; i < array.Length; i++)
      if (array[i] != array[i - length])
      {
        validCycle = false;
        break;
      }
    if (validCycle)
      return length;
  }
}
/// <summary>
/// Attempt to continue an array of integers.
/// </summary>
/// <param name="array">Sequence to extend.</param>
/// <returns>Best guess for next number in sequence.</returns>
public static int ExtendSequence(this int[] array)
{
  // Handle special cases.
  // Empty pattern.
  if (array == null || array.Length == 0)
    return 0;

  // Pattern containing one element.
  if (array.Length == 1)
    return array[0];

  // Pattern containing only identical elements (very common case).
  bool constantPattern = true;
  for (int i = 1; i < array.Length; i++)
    if (array[0] != array[i])
    {
      constantPattern = false;
      break;
    }
  if (constantPattern)
    return array[0];

  // Pattern containing only constantly incrementing elements (very common case).
  constantPattern = true;
  int dx = array[1] - array[0];
  for (int i = 2; i < array.Length; i++)
    if ((array[i] - array[i - 1]) != dx)
    {
      constantPattern = false;
      break;
    }
  if (constantPattern)
    return array[array.Length - 1] + dx;

  // We have a complicated pattern.
  // Try and find a cyclical repeat of pattern elements.
  // At this time we always insist the pattern must start at the beginning of the array.
  int patternLength = FindCycle(array);
  if (patternLength > 0)
  {
    int repeats = array.Length / patternLength;
    int offset = array.Length - (repeats * patternLength);
    return array[offset];
  }

  // If there is no cyclical repeat of pattern elements,
  // there may still be a cyclical repeat of element increments.
  int[] increments = ToDifferenceArray(array);
  patternLength = FindCycle(increments);
  if (patternLength > 0)
  {
    int repeats = increments.Length / patternLength;
    int offset = increments.Length - (repeats * patternLength);
    return array[array.Length - 1] + increments[offset];
  }

  // Being unable to find a pattern, let's just return the last element.
  return array[array.Length - 1];
}

继续整数数组的模式

Continuing a pattern of integer arrays

algorithm

statistics

pattern-matching

prediction