問題タブ [sequences]

Edited after getting answers

Some excellent answers here. I like Josh's because it is so clever and uses C++. However I decided to accept Dave's answer because of it's simplicity and recursion. I tested them both and they both produced identical correct results (although in a different order). So thanks again everyone.

Say I have a string s of chars s[0]:s[N] and where each char s[i] <= s[i+1] For example the string

I want to generate all combinations of substrings while keeping the same relationship between chars.

So for example I would get

But not

Now I know how to work out how many combinations there are. You create a histogram of the frequency of letters in the string. So in the above example the that would be

For string aaacdddghzz

and the formula is (a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384. There are 384 substrings that keep the s[i] <=s [i+1] relationship.

So the question is how do I generate those 384 substrings recursively? Actually an iterative method would be just as good, maybe better as large strings with many unique chars might cause the stack to overflow. This sounds like homework but it isn't. I'm just useless at coming up with algorithms like this. I use C++ but pseudocode would be fine.

f# の morris seq 用に書いたこの「学習コード」がありますが、回避方法がわからないスタック オーバーフローに悩まされています。"morris" は、無限の "see and say" シーケンス (つまり、{{1}、{1,1}、{2,1}、{1,2,1,1}、{1,1,1) を返します。 ,2,2,1}, {3,1,2,2,1,1},...})。

Seq.nth を使用して n 番目の反復を選択できますが、スタック オーバーフローに達する前にしか取得できません。私が持っている再帰の 1 つのビットは末尾再帰であり、本質的にリンクされた一連の列挙子を構築します。問題はそこじゃない。4000番目のシーケンスで「enum」が呼び出されたときです。F# 1.9.6.16 では、以前のバージョンは 14000 を超えていたことに注意してください)。これは、リンクされたシーケンスが解決される方法によるものです。シーケンスは遅延しているため、「再帰」も遅延しています。つまり、seq n は seq n-1 を呼び出し、seq n-2 を呼び出し、以下同様に最初の項目を取得します (最初の # が最悪のケースです)。

が問題を悪化させていることを理解しており[|0|] |> Seq.append str |> Seq.windowed 2、それを排除すれば、生成できる # を 3 倍にすることができます。実際には、コードは十分に機能します。morris の 3125 回目の反復は、長さが 10^359 文字を超えます。

私が実際に解決しようとしている問題は、遅延評価を保持し、選択できる反復のスタック サイズに基づいて制限をなくす方法です。メモリ サイズに基づいて制限を行うための適切な F# イディオムを探しています。

2010年10月更新

F# をもう少しよく学び、Haskell を少し学び、この問題を 1 年以上考え、調査した結果、ようやく自分の質問に答えることができました。しかし、難しい問題はいつもそうですが、問題は間違った質問から始まります。問題はシーケンスのシーケンスではありません。実際には、再帰的に定義されたシーケンスが原因です。私の関数型プログラミングのスキルは少し良くなったので、以下のバージョンで何が起こっているのかを簡単に確認できます。

これは基本的に、シーケンスを生成するための Seq 処理関数呼び出しの非常に長いチェーンを作成します。F# に付属している Seq モジュールは、スタックを使用しないとチェーンをたどることができないものです。追加および再帰的に定義されたシーケンスに使用する最適化がありますが、その最適化は、再帰が追加を実装している場合にのみ機能します。

だからこれはうまくいく

そして、これはスタックオーバーフローを取得します。

F# ライブラリが問題であることを証明するために、継続を使用して追加、ペアワイズ、スキャン、および収集を実装する独自の Seq モジュールを作成しました。これで、問題なく 50,000 seq の生成と出力を開始できます (処理が終了したため、終了することはありません)。 10^5697 桁の長さ)。

いくつかの追加メモ:

• 継続は私が探していたイディオムでしたが、この場合は、私のコードではなく、F# ライブラリに入る必要がありました。F# の継続については、Tomas Petricek の Real-World Functional Programmingの本から学びました。
• 私が受け入れた怠惰なリストの回答は、別のイディオムを保持していました。遅延評価。書き直したライブラリでは、遅延型を利用してスタックオーバーフローを回避する必要もありました。
• 怠惰なリストバージョンは運によって機能します（おそらく設計によるものですが、それは私の現在の判断能力を超えています）-構築および反復中に使用されるアクティブパターンマッチングにより、必要な再帰が深くなりすぎる前にリストが値を計算するため、怠惰ですが、スタックオーバーフローを避けるために継続が必要なほど怠惰ではありません。たとえば、2 番目のシーケンスが 1 番目のシーケンスの数字を必要とするときには、すでに計算されています。つまり、LL バージョンは厳密にはシーケンス生成の JIT 遅延ではなく、リスト管理のみです。

ここでいくつかのこと：

1. ANSI コンソールのエスケープ シーケンスをデコードする C コードを教えてもらえますか?
2. Cygwin BASH で古い TTY をエミュレートする方法はありますか?

多分これは2つの質問であるべきです。

ありがとう。

まず、各構造固有のシーケンスには、アイテムを削除するさまざまな方法があると思います。ベクトルはインデックスによるものであり、リストは最初または最後に削除される可能性があり、セットは削除する実際のアイテムを渡す必要があるなどです。

第二に、構造にとらわれない除去方法がいくつかあると思います。それらはseqインターフェイスで動作します。

Clojure ではシーケンスは不変であるため、実際に行っていることは、元のアイテムを除いて、元の安価なコピーを作成していると思われます。これは、リスト内包表記を削除に使用できることを意味しますが、不必要に冗長になるのではないかと思います。

Clojure シーケンスからアイテムを削除するさまざまな方法の慣用的な例をいくつか挙げてください。

難しい質問でごめんなさい。

次のように、数字を追加するか、数字を置き換える（何も削除しない）ことで修正するシーケンスのセットがたくさんあります。

• 1,2、、3 => 1,7,4,3
• 4、、5、6 => 4,4、5、6
• 4,7,8,9 => 4,7,8,9,1
• 4,7 => 4,8
• 4,7,1 => 4,7,2

それは、パディングされた元のシーケンスとサンプル修正から始まります。

修正されるさまざまなn-gramの頻度を計算することにより、シーケンスを自動的に修正できるようにしたいと思います。最初のサンプルは次のようになります。

• 1 => 1
• 2 => 7
• 3 => 3
• 1,2 => 1,7
• 2,3 => 7,4,3
• 1,2,3 => 1,7,4,3

これらのn-gram補正の頻度を収集し、サンプルデータに含まれる場合と含まれない場合がある新しい入力を補正するための最良の方法を計算する方法を探しています。

これはSMTに似ているようです。

私はクラス階層を持っています:

ノート：

• 基本クラス ジェネレーターは特に必要ないので、削除しても問題ありません。
• 該当する場合、これは Oracle 9i データベースです。
• 休止状態 3.4 JPA
• Spring 2.5も利用可能です

ありがとう

パターン ( e\d\d) を複数回一致させ、それぞれをグループに取り込む方法はありますか? たとえば、文字列..

..4 つのグループを取得したい:

使用する明白な正規表現は (Python 正規表現では:

..しかし、次のいずれかに一致させたい:

できないように見える、という(e\d\d)+かできますが、最後の出現のみをキャプチャします。

TV エピソードのファイル名に一致する複数のパターンがあり、複数のエピソードを処理するために各式を複製したくないため、これを 1 つの正規表現で実行したいと考えています。

..その他多数のパターンについても同様です。

問題を複雑にするもう1つのこと-これらの正規表現を構成ファイルに保存したいので、複数の正規表現と関数呼び出しを使用するソリューションは望ましくありません-しかし、これが不可能であることが判明した場合は、ユーザーが単純な正規表現を追加できるようにします

基本的に、正規表現を使用して繰り返しパターンをキャプチャする方法はありますか?

それぞれの長さの文字列 と の 2 つの有限シーケンスが与えられAた場合、たとえば、次のようになります。Bn

A と B の濃度が同じ文字列になるように、インデックスの有限シーケンスを指定します。繰り返しが許可されています。

この例では解決策を見つけることができませんが、たとえば、リスト(1,2,2,4)が解決策である場合はA1 + A2 + A2 + A4 = B1 + B2 + B2 + B4. この例では 2 人のキャラクターしかいませんが、すでに非常に困難です。実際、1 つの文字で最短の解決策を見つけることは簡単なことではありません。

私は物事を考えようとしました..たとえば、文字列の長さの合計は等しくなければならず、最初と最後の文字列には対応する文字が必要です。しかし、他には何もありません。いくつかの文字列のセットでは、それは単に不可能だと思います。誰でも良いアルゴリズムを思いつくことができますか?

編集：どうやら、これは通信後の問題です

そのようなインスタンスに解があるかどうかを判断できるアルゴリズムはありません。もしあれば、停止の問題は解決できます。汚い手口...

ベクトルは seq ではなく、リストは seq であると読みました。どちらか一方を使用する理由が何であるかはわかりません。ベクターが一番使われているようですが、それには何か理由があるのでしょうか？

自動音楽制作に興味があります。私は、多数の 1 小節のアルペジオ (= 簡単にするために固定長の音符のシーケンス) が与えられ、学習した内容に基づいて独自のシーケンスを生成するプログラムについて考えていました。

まず、文字 (ダイグラム? トライグラム?)の周波数分析を使用して、音程のみに適用し、周波数確率に基づいてシーケンスを生成できることを知っています。

あなたが知っているより高度なアルゴリズムはありますか?おそらく音楽シーケンス用に明示的に教えられていますか?