0から1000の間のすべての数字を含む最短の文字列は何ですか。

Question

私は机に座っています。問題を考えただけです。誰かが解決策や方法を考え出すことができるかどうか疑問に思っていました。これは数学的に

0から1000の間のすべての数値を含む最短の文字列を探したいとします。たとえば、「1433」という文字列には、1,4,4,3,14,43,33,143、 433.

0から1000までのすべての数値を含む最短の文字列を作成するために、どのアルゴリズムを使用できますか。

私は知りたいと思う実用的な理由はありませんが、もしあれば聞くことに興味があります。

Answer 1

変更されたde Bruijn sequenceを求めています。具体的には、最初のn-1文字が文字列の最後に付加されたde Bruijnシーケンス。

あなたが尋ねる特定のケースでは、10^3 + 2 = 1002桁の長さになります（1000が含まれていないと仮定します）。任意に選択された（10,3）de Bruijnシーケンスに "1000"が含まれるという保証はありません）。