深さ優先探索の探索順配列モデルの生成

個人開発したアプリの宣伝
目的地が設定できる手帳のような使い心地のTODOアプリを公開しています。
Todo with Location

Todo with Location

  • Yoshiko Ichikawa
  • Productivity
  • Free

お勉強がてら書いてみた。

こういう数値リストを

[5, 20, 22, 35, 64, 71]

組み合わせごとの探索順のツリーにする。

言語はvar_dumpが綺麗なPHPで。

<?php
// Your code here!
$num_list = array( 5, 20, 22, 35, 64, 71 );
function search( $num_list, $index ){
    $arrayCount = count( $num_list );
    //底まで探索
    if( !array_key_exists( $index+1, $num_list ) ){
        return array( $num_list[$index] );
    }
    
    $child = array();
    //loopは現在のindexから配列の終端まで
    for($i=1;$i<$arrayCount-$index;$i++){
        //子ノードを作成 現在のindex以降のtreeを持つ
        $child[] = search( $num_list, $index+$i);
    }
    //ノードを親に返す [ value, [children] ]
    return array( $num_list[$index], $child );
}

$data = search($num_list, 0);
var_dump($data);
?>
array(2) {
  [0]=>
  int(5)
  [1]=>
  array(5) {
    [0]=>
    array(2) {
      [0]=>
      int(20)
      [1]=>
      array(4) {
        [0]=>
        array(2) {
          [0]=>
          int(22)
          [1]=>
          array(3) {
            [0]=>
            array(2) {
              [0]=>
              int(35)
              [1]=>
              array(2) {
                [0]=>
                array(2) {
                  [0]=>
                  int(64)
                  [1]=>
                  array(1) {
                    [0]=>
                    array(1) {
                      [0]=>
                      int(71)
                    }
                  }
                }
                [1]=>
                array(1) {
                  [0]=>
                  int(71)
                }
              }
            }
            [1]=>
            array(2) {
              [0]=>
              int(64)
              [1]=>
              array(1) {
                [0]=>
                array(1) {
                  [0]=>
                  int(71)
                }
              }
            }
            [2]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [1]=>
        array(2) {
          [0]=>
          int(35)
          [1]=>
          array(2) {
            [0]=>
            array(2) {
              [0]=>
              int(64)
              [1]=>
              array(1) {
                [0]=>
                array(1) {
                  [0]=>
                  int(71)
                }
              }
            }
            [1]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [2]=>
        array(2) {
          [0]=>
          int(64)
          [1]=>
          array(1) {
            [0]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [3]=>
        array(1) {
          [0]=>
          int(71)
        }
      }
    }
    [1]=>
    array(2) {
      [0]=>
      int(22)
      [1]=>
      array(3) {
        [0]=>
        array(2) {
          [0]=>
          int(35)
          [1]=>
          array(2) {
            [0]=>
            array(2) {
              [0]=>
              int(64)
              [1]=>
              array(1) {
                [0]=>
                array(1) {
                  [0]=>
                  int(71)
                }
              }
            }
            [1]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [1]=>
        array(2) {
          [0]=>
          int(64)
          [1]=>
          array(1) {
            [0]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [2]=>
        array(1) {
          [0]=>
          int(71)
        }
      }
    }
    [2]=>
    array(2) {
      [0]=>
      int(35)
      [1]=>
      array(2) {
        [0]=>
        array(2) {
          [0]=>
          int(64)
          [1]=>
          array(1) {
            [0]=>
            array(1) {
              [0]=>
              int(71)
            }
          }
        }
        [1]=>
        array(1) {
          [0]=>
          int(71)
        }
      }
    }
    [3]=>
    array(2) {
      [0]=>
      int(64)
      [1]=>
      array(1) {
        [0]=>
        array(1) {
          [0]=>
          int(71)
        }
      }
    }
    [4]=>
    array(1) {
      [0]=>
      int(71)
    }
  }
}