c#で再帰関数を使った順列の求め方
Posted: 2016年9月27日(火) 20:10
Unityでゲームを製作中なのですが、AIなどのルート検索にバックトラックと言うものがあると知り、再帰関数を
知って実践しようと、まずは簡単な順列をと思ったのですが、試行錯誤してもうまく行かずに悩んでおります。
やりたいことは、ABCDという文字列の順列を作ることで、手法としてはList ABCDの中に並べ替える文字を入れ、resultの中に
結果を入れていく。樹形図の選択肢のように、選択できる文字列は減っていくために消去していく。
resultの文字数が4文字になったら再帰をやめ、結果を出力
症状としては、4回再帰したあと、樹形図の末端から一つ戻って
for(int i =0; i <ABCD.Count; i++)
この部分の i の値が1となってとなるはずが、ループせずにresultを4回出力して終わってしまうという状況です。
また、出力結果はa b c dが4回表示されるだけです。
知って実践しようと、まずは簡単な順列をと思ったのですが、試行錯誤してもうまく行かずに悩んでおります。
やりたいことは、ABCDという文字列の順列を作ることで、手法としてはList ABCDの中に並べ替える文字を入れ、resultの中に
結果を入れていく。樹形図の選択肢のように、選択できる文字列は減っていくために消去していく。
resultの文字数が4文字になったら再帰をやめ、結果を出力
症状としては、4回再帰したあと、樹形図の末端から一つ戻って
for(int i =0; i <ABCD.Count; i++)
この部分の i の値が1となってとなるはずが、ループせずにresultを4回出力して終わってしまうという状況です。
また、出力結果はa b c dが4回表示されるだけです。
using UnityEngine;
using System.Collections;
using System.Linq;
using System.Collections.Generic;
public class test : MonoBehaviour {
// Use this for initialization
void Start () {
List<string> result = new List<string>();
List<string> ABCD = new List<string>() { "a","b","c","d"};
permutation(ABCD, result);
}
void permutation(List<string> ABCD,List<string> result)
{
for(int i =0; i <ABCD.Count; i++)
{
result.Add(ABCD[i]);
ABCD.RemoveAt(i);
if(result.Count != 4)
{
permutation(ABCD, result);
}
}
string[] tmp = result.ToArray();
Debug.Log(string.Join(",",tmp));
}
}