TypeScriptを活用した階層構造データのランダム生成テクニック

こんにちわ。nap5です。

TypeScriptを活用した階層構造データのランダム生成テクニックの紹介です。

世代データだけに限らず、いろいろ応用が利きそうです。

実装です。

type Item = {
  id: number;
  name: string;
};

type TreeNode = {
  id: number;
  name: string;
  children: TreeNode[];
};

type Visited = Set<number>;

const itemFactory = (
  items: Item[],
  visited: Visited,
): (() => [Item, Visited]) => {
  return (): [Item, Visited] => {
    const availableItems = items.filter((item) => !visited.has(item.id));
    if (availableItems.length === 0) {
      throw new Error("No more available items to choose from.");
    }
    const randomIndex = Math.floor(Math.random() * availableItems.length);
    const selectedItem = availableItems[randomIndex];
    visited.add(selectedItem.id);
    return [selectedItem, visited];
  };
};

const clamp = (value: number, min: number, max: number): number => {
  return Math.min(Math.max(value, min), max);
};

const makeData = (seriesItems: Item[][], ...lens: number[]): TreeNode[] => {
  for (let i = 0; i < lens.length; i++) {
    if (lens[i] > seriesItems[i].length) {
      throw new Error(
        `The number of items selected (${lens[i]}) cannot be greater than the number of items in the seed list (${seriesItems[i].length}).`,
      );
    }
  }

  const makeDataLevel = (
    depth: number = 0,
    visited: Visited = new Set(),
  ): TreeNode[] => {
    const availableItems = seriesItems[depth].filter(
      (item) => !visited.has(item.id),
    );
    const actualLen = clamp(lens[depth], 0, availableItems.length); // Use the length of availableItems here
    const getItem = itemFactory(seriesItems[depth], visited);

    return Array.from({ length: actualLen }).map((): TreeNode => {
      const [item, newVisitedForItem] = getItem();
      // Pass the 'newVisitedForItem' set to the recursive call instead of creating a new set
      const children = lens[depth + 1]
        ? makeDataLevel(depth + 1, newVisitedForItem)
        : [];
      children.forEach((child) => {
        newVisitedForItem.add(child.id); // Add the ids of the children to the visited set
      });
      return {
        ...item,
        children,
      };
    });
  };

  return makeDataLevel();
};

// 上の世代には少なめのバリエーション、下の世代には多めのバリエーションを設ける
// こうすることで、Populatedされたデモデータが作られやすくなります
const generation1: Item[] = [
  { id: 1, name: "Adam" },
  { id: 2, name: "Eve" },
  { id: 3, name: "Lilith" },
  { id: 4, name: "Lucas" },
];

const generation2: Item[] = [
  { id: 5, name: "Cain" },
  { id: 6, name: "Abel" },
  { id: 7, name: "Seth" },
  { id: 8, name: "Nina" },
  { id: 9, name: "Ian" },
  { id: 10, name: "Aria" },
];

const generation3: Item[] = [
  { id: 11, name: "Enos" },
  { id: 12, name: "Kenan" },
  { id: 13, name: "Mahalalel" },
  { id: 14, name: "Eliana" },
  { id: 15, name: "Nolan" },
  { id: 16, name: "Dara" },
];

export const generateDemoData = (): TreeNode[] => {
  return makeData([generation1, generation2, generation3], 1, 2, 3);
};

demo code.

great-kalam-cxtgsn

簡単ですが、以上です。