遞歸

引言

我自己寫了一個命令行todo任務管理清單，中間涉及到層級排序問題。這是一件很好的事情：讓我發現此前對遞歸的理解是錯誤的，也正因為我幾乎不會用到它。

文中演示內容基於node.js運行環境。

層級

結構

考慮對這樣一個數據結構排序：

1
2
3
4
5
6
7
8
9
10
11
let list = [
  [['A', 'C'], ['1111']],
  [['A', 'D'], ['1111']],
  [['B', 'E'], ['1111']],
  [['A', 'D'], ['2222']],
  [['B', 'E'], ['2222']],
  [['B', 'F'], ['1111']],
  [['A', 'D'], ['3333']],
  [['B', 'E'], ['3333']],
  [['A', 'D'], ['4444']],
]

清單list中的某一項，譬如 [['A', 'C'], ['1111']]。其中['A', 'C']是一個關於標籤A與C的集合，而後一項['1111']是目前只包含一項1111內容的集合。我的數據結構不完全與其相似，只是出於簡便起見而抽象如此。

我期望將其打印為

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B
  F
    1111
  E
    1111
    2222
    3333
A
  C
    1111
  D
    1111
    2222
    3333
    4444

即每個節點按其包含分支總數排序，由少及多。

排序

如果對已經生成的層級結構排序，這是一件困難的事情。我想到的一個簡便的辦法是在初始時刻進行排序。排序的依據是對list中的每一項進行估值，而這個值要滿足層級結構的條件。

首先統計標籤數量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function countTag(list) {
  let tagsCount = {total: list.length};
  for (item of list) {
    let tags = item[0];
    for (tag of tags) {
      if (tag in tagsCount) {
        tagsCount[tag] += 1;
      } else {
        tagsCount[tag] = 1;
      }
    }
  }
  return tagsCount;
}

這樣得到的tagsCount為

1
2
3
4
5
6
7
8
9
tagsCount = { 
	total: 9, 
	A: 5, 
	C: 1, 
	D: 4, 
	B: 4, 
	E: 3, 
	F: 1 
}

下一步對list中的每一項估值，生成一個weightedList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function listToSort(list, tagsCount) {
  let weightedList = [];
  for (item of list) {
    let value = 0;
    let weight = 1;    
    let tags = item[0];
    for (idx in tags) {
      if (idx == 0) {
        weight *= 1/(tagsCount.total + 1);
      } else {
        weight *= 1/(tagsCount[tags[idx - 1]] + 1);
      }
      value += weight * tagsCount[tags[idx]];
    }
    weightedList.push([item, value])
  }
  return weightedList;
}

函數中的weight權值需要仔細設計：要確保父節點權值的量級足夠大，不會受到後續子節點累加效應的干擾。這裡給出的是權值在臨界條件下的關係式。

得到所示的weightedList，相較於原來的list只是多出一列估值

1
2
3
4
5
6
7
8
9
10
11
weightedList = [
  [[['A', 'C'], ['1111']], 0.5166666666666667],
  [[['A', 'D'], ['1111']], 0.5666666666666667],
  [[['B', 'E'], ['1111']], 0.46],
  [[['A', 'D'], ['2222']], 0.5666666666666667],
  [[['B', 'E'], ['2222']], 0.46],
  [[['B', 'F'], ['1111']], 0.42000000000000004],
  [[['A', 'D'], ['3333']], 0.5666666666666667],
  [[['B', 'E'], ['3333']], 0.46],
  [[['A', 'D'], ['4444']], 0.5666666666666667]
]

然後排序就十分簡單了

1
2
3
4
5
6
7
8
function sortList(weightedList) {
  let sortedList = [];
  let sortedWeightedList = weightedList.sort((a, b) => a[1] - b[1]);
  for (item of sortedWeightedList) {
    sortedList.push(item[0]);
  }
  return sortedList;
}

得到重新排序的sortedList，打印出來是這樣

1
2
3
4
5
6
7
8
9
[ [ 'B', 'F' ], [ '1111' ] ]
[ [ 'B', 'E' ], [ '1111' ] ]
[ [ 'B', 'E' ], [ '2222' ] ]
[ [ 'B', 'E' ], [ '3333' ] ]
[ [ 'A', 'C' ], [ '1111' ] ]
[ [ 'A', 'D' ], [ '1111' ] ]
[ [ 'A', 'D' ], [ '2222' ] ]
[ [ 'A', 'D' ], [ '3333' ] ]
[ [ 'A', 'D' ], [ '4444' ] ]

與原先的list基本相同，只是次序發生變化。

轉化

清單list中的每一項，譬如第一項 [['A', 'C'], ['1111']]，我希望將其轉化為一個嵌套結構，譬如

1
{A: {C: {list: [1111]}}}

內部有一個名為list的key，它是不必要的，但加上可以省掉很多麻煩，譬如在需要判斷此處是否為最末端節點時，你也可以用別的名字。

用遞歸處理是非常簡單的

1
2
3
4
5
6
7
8
9
10
11
12
13
function convertOneRecord(tags, stringList, record = false) {
  if (tags.length == 0) {
    return record;
  } else {
    let tag = tags.pop();
    if (record) {
      record = {[ tag ]: record};
    } else {
      record = {[ tag ]: { list: stringList}};
    }
    return convertOneRecord(tags, stringList, record);
  }
}

譬如對list的第一項執行convertOneRecord(list[0][0], list[0][1])即可得到期望的結果。

合併

然後把這些轉化的一條條紀錄合併起來，還是用到遞歸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function merge(main, branch) {
  let keys = Object.keys(branch);
  if (keys.includes('list')) {
    if (Object.keys(main).includes('list')) {
      main.list.push(branch.list[0]);
    } else {
      main.list = branch.list;
    }
  } else {
    let key = keys[0];
    if (Object.keys(main).includes(key)) {
      main[key] = merge(main[key], branch[key]);
    } else {
      main[key] = branch[key];
    }
  }
  return main;
}

因為涉及到多重邏輯判斷，寫起來非常容易出錯，需要記住判斷後面必須要有返回值，否則會出現undefined的錯誤。如果沒有錯誤的話就可以得到完整的層級數據。

譬如對排序好的sortedList執行

1
2
3
4
5
6
7
8
let tagsCount = countTag(list);
let weightedList = listToSort(list, tagsCount);
let sortedList = sortList(weightedList);
let convertedSortedList = {};
for (item of sortedList) {
  let convertedOneRecord = convertOneRecord(item[0], item[1]);
  convertedSortedList = merge(convertedSortedList, convertedOneRecord);
}

得到convertedSortedList大約是這樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
convertedSortedList = {
	B: {
		F: {
			list: ['1111']
		},
		E: {
			list: ['1111', '2222', '3333']
		}
	},
	A: {
		C: {
			list: ['1111']
		},
		D: {
			list: ['1111', '2222', '3333', '4444']
		}
	}
}

打印

打印層級數據的方式有很多種，譬如命令行軟件tree，如果你也想要那些連在一起的漂亮線段的話。原理都是相似的，只是處理起來要稍微麻煩一點。出於簡單起見我只考慮最簡單的縮進方式表現層級，這裡還是要用到遞歸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function printHierarchy(hierarchy, level = 0) {
  if (Object.keys(hierarchy).includes('list')) {
    for (item of hierarchy.list) {
      let string = '  '.repeat(level);
      console.log(string + '  ' + item);
    }
  } else {
    for (key in hierarchy) {
      let string = '  '.repeat(level);
      console.log(string + '  ' + key);
      printHierarchy(hierarchy[key], level + 1);
    }
  }
}

執行printHierarchy(convertedSortedList)即可得到最後期望的結果。

後記

我很少寫這類文章，寫程序實在是一件小兒科的事情。緣故是我在起初以為這是一個簡單的問題，而後我發現似乎沒那麼容易。我在stackoverflow上只找到一個類似的回答，實際上我也沒看懂，那個回答多半是錯誤的。

我決定自己動手寫，這種事情還要用庫就太可笑了。我的思路就是文中所示的那樣：將其分拆成若干塊分別處理。我不清楚一般程序員是如何處理這些問題，至少在我更習慣從數學上理解它。譬如一般的排序問題，我會定義一個熵函數，然後證明每一次交換總是向遞減方向進行，這種操作不會超出最大交換次數等等，而程序員似乎更多是從經驗處理問題。

當然經驗是一個好東西，我不會否認這一點。