-1

長さの異なる2つの配列があります。それらをハッシュに入れて、要素をできるだけ均等に分散させたいと思います。

編集：申し訳ありませんが、私は十分な入力を提供していないことに気づきました。「可能な限り均等に」とは、次のことを意味します。

array1には、常にarray2よりも多くの要素があります。

array2要素は文字列です。最小単位は単語です。

UPATED GOAL 結果のハッシュについて、平均的な単語と数値の比率（すべての要素array2からarray1.join（ ""）.split（ ""））に基づいてキーに値を分散させたい。文字列の整合性を損なうことなく、可能な限り平均に近い数値を文字列に分散させるためです。結果を次のように表示することもできます。

result = {"The older son of a woman" =>[320, 321, 322, 323],...}

混乱して申し訳ありませんが、アプリケーションの目的によって、これを逆に考えさせられたと思います。

以下のサンプルコードが機能する場合もありますが、機能しない場合もあります。

array1.clear
array2.clear

array11 = [336, 337, 338, 339, 340, 342, 344, 345, 346, 347, 348]
array22 = ["New research", "suggests that hoarders have unique patterns", "of brain activity", "when faced with making decisions", "about their possessions."] 

array1 =  [320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 331, 332, 333, 334] 
array2 = ["The older son of a woman", "killed at Sunday's mass shooting", "in Wisconsin said she was shot just", "after completing prayers."] 


def hash_from_arrays(array1, array2)
 hash  =  Hash.new{|h,k| h[k] = [] }
  arr_ratio = arr1_to_arr2_ratio(array2, array1)
  start =  0
  last_arr1_to_arr2 = Float(Float(array2.last.split(" ").length)*Float(arr_ratio)).floor
  array1.each_with_index do | element, index|
    arr1_for_arr2_ratio = Float(Float(array2[0].split(" ").length)*Float(arr_ratio)).floor
    hash[element] = array2[0]
    if arr1_for_arr2_ratio + start == index && array2.length > 1
      array2.shift
      start = index
    end
  end
  return hash
end



def arr1_to_arr2_ratio(array1, array2)
  word_count = 0.0
  array1.each{|string| word_count = word_count + string.split(" ").length}
  result = Float(array2.length) / word_count
  return result
end



 hash_from_arrays(array1, array2)
 => {320=>"The older son of a woman", 321=>"The older son of a woman", 322=>"The older son of a woman", 323=>"The older son of a woman", 324=>"The older son of a woman", 325=>"killed at Sunday's mass shooting", 326=>"killed at Sunday's mass shooting", 327=>"killed at Sunday's mass shooting", 328=>"in Wisconsin said she was shot just", 329=>"in Wisconsin said she was shot just", 331=>"in Wisconsin said she was shot just", 332=>"in Wisconsin said she was shot just", 333=>"after completing prayers.", 334=>"after completing prayers."}

編集コードを更新しました。両方のアレイで機能するようになりました。一般的には機能すると思います...誰かがより良い解決策を提案できれば、それは素晴らしいことです。

4

2 に答える 2

1

私はあなたがいくつかの解決策を持っていることをうれしく思います:)

私はあなたのnevestコードで少し遊んだことがあります、持っていましょう：

array1 =  [320, 321, 322, 323, 324]
array2 = ["a a a a a a a a a a a a a a a a", "b"]

irb(main):071:0> pp hash_from_arrays(array1, array2)
{320=>"a a a a a a a a a a a a a a a a",
 321=>"a a a a a a a a a a a a a a a a",
 322=>"a a a a a a a a a a a a a a a a",
 323=>"a a a a a a a a a a a a a a a a",
 324=>"a a a a a a a a a a a a a a a a"}

1）「B」を全く使わなくても大丈夫ですか？
2）array2には17ワードがあり、array1の5つのキーで割った値=キーあたり平均3.4ワード。結果は、キーごとに平均16ワードになります。これは、3.4からはかなり遠いです。明らかに、「b」が数回使用された場合、平均は3.4に近くなります。

それとも、あなたがどのような分布/平均を考えているのか理解できなかったのでしょうか？

于 2012-08-11T01:11:55.607 に答える
1

0）問題の説明：

2つのセットがあり、それらの間のマッピングを定義したいと思います。

1つ目は、SSまたは「strings」という名前の一意の文字列のセットであり、その項目は「文字列」と呼ばれます。
最初のセットは有限であり、NStringsアイテムで構成されています。
最初のセットの各文字列は、NumWords（string）で示される任意の数の単語で構成できます。
したがって、最初のセットは、TargetAVGで示される、文字列ごとの平均単語数の統計プロパティも提供します。

2つ目は、KKまたは「キー」という名前の一意の番号のセットであり、そのアイテムは「キー」と呼ばれます。
2番目のセットは有限であり、NKeysアイテムで構成されています。
これらの数値の正確な値は関係ありません。一意の識別子として使用されます。

2番目のセットには最初のセットよりも多くのエントリがあることが保証されています。

最初のセットと2番目のセットの間にマッピングMMを生成したいと思います。
2番目のセット（キー）のすべてのアイテムには、最初のセット（文字列）の1つのアイテムだけを割り当てる必要があります。
このマッピングでは、最初のセット（文字列）の各アイテムを少なくとも1回使用する必要があります。
最初のセット（文字列）の任意のアイテムを複数回使用できます。
したがって、マッピングは、NumUses（string）で示される、最初のセット（strings）からの特定のアイテムの使用回数の統計プロパティも生成します。

キーに割り当てられた文字列内の単語数がTargetAVGの同じ平均（または可能な限り近い）を生成し、文字列が平均の数倍になるというコメントを付けて、このようなマッピングを生成したいと思います。マッピングで使用された回数。

1）言い換える：

問題：

目標の総価値に最適な一意のアイテムの固定セットから、値の異なるアイテムの固定数を選択します。選択するアイテムの数がアイテムの数よりも多いため、このいくつかのアイテムは何度も選択する必要があります。

追加の制限：

各項目は少なくとも1回は選択する必要があります。

どこ：

items =SS
ターゲットアイテム数=NKeys
アイテム値=NumWords（item）* NumUses（item）
ターゲット合計値= TargetAVG * NKeys（=マッピング全体の単語の推定合計量）

2）問題の複雑さを軽減してみましょう。

文字列よりも多くのキーがあります+各文字列は少なくとも1回使用する必要があります+各キーは正確に1回使用する必要があります。
したがって、適切に生成されたマッピングには、異なるキーにマップされたすべての文字列で構成されるサブセットが含まれます。
したがって、キーのNStringはすでに部分的に解決されています。これは、キーが各文字列と1対1で一致する必要があることがわかっているため、順序がわからないためです。たとえば、70個のキーのうち約30個を30個の文字列のそれぞれに1対1でペアリングする必要があることはわかっていますが、どのキーをどの文字列に接続するかはわかりません。ただし、割り当ての正確な順序は決して重要ではなかったため、最初から1番目、2番目から2番目、...30番目から30番目のようにまっすぐにマッピングすることもできます。
そして、これはまさに私たちが問題を減らすために行うことです。

したがって：

-）文字列よりも多くのキーがあったため、常に削減できます
-）これに代わって、常にいくつかの残りのキーが残ります（NKeys-NStrings）
-）「各アイテムは少なくとも1回は選択されました」

健全性チェック：
部分的なソリューションはキーのNStringを使い果たし、（NKeys-NStrings）キーが残っています。
最終的なソリューションは、TargetAVGに等しい平均を達成する必要があります。
キーの最初のNStringに対して、文字列のすべてのNStringをすでに使用しました。
これは、部分的なソリューションの内部平均が「TargetAVG」であることが保証されていることを意味します。
いくつかの鍵が残っています。
これは、残りのキーのマッピングも「TargetAVG」の平均、または可能な限り近い必要があることを意味します。
要件を満たしました。これで、ゼロでも、いつでも任意の文字列を使用できます。

すべてが素晴らしいですね。

3）残りの問題：

問題の種類：

目標の総価値に最も合うように、固定数の価値のあるアイテムを選択します。どのアイテムでも何度でも選択できます。

どこ：

items = SS
ターゲットアイテム数=（NKeys-NStrings）
アイテム値= NumWords（item）* NumUses（item）
ターゲット合計値= TargetAVG *（NKeys-NStrings）（=残りのマッピングの推定合計単語数）

重要なことは、正確な「X」個のピックを使用して、指定された値「S」に最も近い合計を求めていることです。
これは、一般的なナップザックパッキング問題ではなく、そのサブクラスの一種であり、 変更を加える問題の一種であることを意味します。それがそれに合うかどうか試してみましょう：

価値の異なるコインの使用を最小限に抑えて、ある金額の現金を処理する必要があります。
=>
正確にXピックを使用して、指定された量の単語を異なる単語数のいくつかの文字列間で分割する必要があります。

さらに、理想が不可能な場合に備えて、「最適な」結果を得たいと考えています。

ナップサック問題はNPとして分類され、正確な、または可能な限り最良の問題を取得することは、一般的に困難であるか、非常に時間がかかります。グーグルでしばらく過ごした後、私は正確なNピックでお金の問題を解決するすぐに使えるアルゴリズムを見つけられませんでした、そしておそらくそのクラスの問題は単に他の名前で知られています、それは今思い出せません。そのような問題をどのように分類するかを検索するか、質問することを強くお勧めします。アルゴリズムの命名法に精通している人が答えれば、すぐに実用的な解決策が見つかるかもしれません。

考慮すべき他の事柄：あなたの「最良の結果」の必要性はどれほど深刻であり、実際、それはどれだけ近くにある必要がありますか？文字列の数に対してどのくらいのキーがありますか？文字列の単語数はどのくらい異なりますか？それに関する追加の条件は、ナップザックを落とし、それらの条件でたまたま安全になるいくつかの素朴な方法を使用するのに役立つ可能性があります。

たとえば、残りの数（NKey-NSstrings）が少ない場合は、すべての可能性をチェックする完全な指数検索を実行するだけで、確実に最良の結果が得られます。

そうでなければ、最高の結果を必要とせず、（NKeys-NStrings）が高く、単語数が比較的均等な形である場合は、単純な貪欲な割り当てを行うことができ、誤って割り当てられたいくつかの項目は平均を少しだけずらします（いくつかの項目を高いNKeys-NStrings =平均の低い部分で割ったもの）。

他の場合、または本当に最適な一致が必要な場合は、同様の問題の近似解を生成できる「動的計画法」または「整数線形計画法」に入る必要があります。

それについて何か考えがあれば、追加してコメントを残しますが、実際は疑問です。私の記憶から、私はすべてを書きました、そして私が実際に再びアルゴブックに鼻を突き刺した場合にのみ、あなたにもっと多くのポインターを与えることができました、それは悲しいことに今はほとんど時間がありません:)私をドロップしてください問題の正しい分類を偶然見つけた場合は注意してください。

于 2012-08-12T20:29:10.863 に答える