回形遍历问题

回形遍历问题

问：编写 SpreadOutArrs 函数

console.log(SpreadOutArrs([
  [1,2,3],
  [8,9,4],
  [7,6,5]
]))
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(SpreadOutArrs([
  [1,  2, 3,4],
  [12,13,14,5],
  [11,16,15,6],
  [10, 9, 8,7]
]))
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
console.log(SpreadOutArrs([
  [1,  2, 3, 4,5],
  [16,17,18,19,6],
  [15,24,25,20,7],
  [14,23,22,21,8],
  [13,12,11,10,9]
]))
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

答：找规律

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

思路：回形遍历，首先要找到回形路线的规则，通过有序的回形递增数值展开找规律，展开后为

0，1，2，3，4，9，14，19，24，23，22，21，20，15，10，5，6，7，8，13，18，17，16，11，12

好下面开始找规律，如图：

关键点说明：

n: n是指回形的宽高

l：l是个关键，每一段（环）以l2分，按下标相加得出一个固定值(n² - 1)，【如果是从1开始的则是n²，不过js下标习惯从0开始】；

n-2: n-2是每一环n的递减规律

解：

1、从图中可以看出，每一段的规律是一样的，只是段长度和起始值不同，可以看出，段长度是以n - 2 的规律递减的，因此，可以以一个递归实现：

function order (n) {
		function Shrink (n) {
      const n2 = Math.pow(n, 2) // n²
			if (n2 === 0) return			// n = 0
			if (n2 === 1) {						// n = 1
        // 直接单独处理就好
				return
			}
			Shrink(n-2)
		}
		Shrink(n)
	}

2、怎样得出l，每一环的数量为：

n² - (n - 2)²
// 换算
= n² - (n - 2)*(n - 2)
= n² - n² + 2n + 2n - 4
= 4n - 4
= 4(n - 1)

// 4(n - 1) / 2 就是l的值，2(n - 1)；
// 结果 2(n - 1)

3、根据每一段的规律计算下标

// l 在上文求出
// n 为当前段回形的宽度
let arr = []
let maxN = Math.pow(N, 2) - 1 // 相加固定值，即 n² - 1
let v = 0
for (let i = 0; i < l; i ++) {
  if (i < n) {
    // <n的值就直接推入
    v = i
    arr[i] = v
    // 推入与 v 相加为 maxN的值到对应位置
    arr[l + i] = maxN - v
  } else {
    // >=n的值按规律加值
    v += n
    arr[i] = v
    // 推入与 v 相加为 maxN的值到对应位置
    arr[l + i] = maxN - v
  }
}

以上实现了一段，也就是一个回环的顺时针下标排列，下面将其套入到回环递归中，注意：n的值是在递减，要把n的初始值保存。如下：

function order (n) {
  let result = []
  const initLen = n
  const maxN = Math.pow(initLen, 2) - 1
  function Shrink (n) {
    const n2 = Math.pow(n, 2)
    // ---
    const rI = (initLen - n) / 2 	// 环下标
    const r = rI * (initLen + 1) 	// 环增长值
    let v  = 0										// 循环中前行值
    let arr = []									// 当前环下标集
    // ===
    if (n2 === 0) return
    if (n2 === 1) {
      arr.push(r)
      result = result.concat(arr)
      return
    }
    const l = 2*(n - 1)
    for (let i = 0; i < l; i ++) {
      if (i < n) {
        v = i + r
        arr[i] = v
        arr[l + i] = maxN - v
      } else {
        v += initLen
        arr[i] = v
        arr[l + i] = maxN - v
      }
    }
    result = result.concat(arr)
    Shrink(n-2)
  }
  Shrink(n)
  return result
}
console.log('---------------------------- line --------------------------------')
console.log(order(1))
console.log(order(2))
console.log(order(3))
console.log(order(4))
console.log(order(5))

如上：其中值得一提的是 r 变量的规律，r = 环下标 回形原始宽加1，即 r = rI (initLen + 1)，

至此，我们已经得出了回形遍历的函数方法，可以应用到此类案例中，本文题目就是一个这样的案例，如下解：

function SpreadOutArrs (arr) {
  const n = arr.length
  arr = arr.reduce((a1, a2) => a1.concat(a2))
  const indexArr = order(n)
  const result = []
  indexArr.forEach(i => {
    result.push(arr[i])
  })
  return result
}
console.log('---------------------------- line --------------------------------')
console.log(SpreadOutArrs([
  [1,2,3],
  [8,9,4],
  [7,6,5]
]))
console.log(SpreadOutArrs([
  [1,  2, 3,4],
  [12,13,14,5],
  [11,16,15,6],
  [10, 9, 8,7]
]))
console.log(SpreadOutArrs([
  [1,  2, 3, 4,5],
  [16,17,18,19,6],
  [15,24,25,20,7],
  [14,23,22,21,8],
  [13,12,11,10,9]
]))
// 输出
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]