ピジョンホール原理（離散数学）

Question

私はこの問題のサンプル入力出力を知りたいと思っています。質問は次のとおりです。 "ピジョンホール原理は、関数fにn個の入力があるが、 f（a）= f（b）となるようなaとbを求めるアルゴリズムを提示する。機能入力は1,2、......、nがあること。？私は明確に質問を理解していないです、この問題を解決することができません

。 をあなたの助けを探している。

Answer 1

続けて何をhttps://stackoverflow.com/a/42254627/7256243と言いましたか。 y長さNの配列Aを長さN-1の配列Bにマップする。 結果は配列Bになります。 1つのインデックスに対して2つの要素があります。

A = {1,2,3,4,5,6} 
map A -> B 

可能な解決策がありました。

B= {1,2,{3,4},5,6} 

A - >のマッピングは、任意の数の方法で行うことができます。 この例では、配列Aの入力インデックス3と4の両方が、配列Bの同じインデックスを持ちます。

この便利な情報が必要です。

Answer 2

ステップバイステップで行こう。

私は2つのボックスを持っています。私の父は私に3個のチョコレートをくれました....

そして私はこれらのチョコレートを2箱に入れたいと思います。私たちの利益のためにチョコレートの名前をつけましょうa、b、c。

私たちにはいくつの方法がありますか？

[ab][c] 
[abc][] 
[a][bc] 

あなたは何か変わったことがありますか？少なくとも1つのチョコレートを持つ少なくとも1つの箱があります。

あなたはどう思いますか？

これを任意の数のボックスとチョコレート（複数のボックス以上）で試してみることができます。それが正しいことがわかります。

まあさんはそれをより容易にしてみましょう：

私は5人3つの部屋を持っています。私たちはパーティーをしています。そして今何が起こるか見てみましょう。 （すべての私の友人はいずれかの部屋に座るでしょう）

私は1人以上の友人がいるだろうと少なくとも1つの部屋があると主張しています。

私の友人はかなり間違っていて、私が間違っていることを証明しようとしていることを知っています。

• Friend-1はルーム1を選択します。
• Friend-2さんはroom-1をなぜと考えていますか？それで彼は部屋2を選択するようになります
• フレンド3は同じと思います...彼は1と2の部屋を避けて部屋3に入ります
• Friend-4が来て、他の空室と彼はいくつかの部屋に入る必要があります。そして、私は正しいようになる。

状況を理解していますか？

n人の友人（funtions）が、残念ながら（幸いにも）彼らの部屋（出力値）はnより小さい。だから、のいずれかが2鉱山aの友人と同じ部屋を共有するb。（同じ値f(a)=f(b)）が存在勿論

Answer 3

鳩の巣原理は、あなたが箱よりも多くのアイテムを持っている場合は、ボックスの少なくとも一つは持っていなければならないことを言いますその中の複数の項目。

a！= bがf（a）== f（b）のプロパティを持つアイテムを検索する場合は、ハッシュマップデータ構造を使用するのが簡単です。項目値xを格納するために、関数値f（x）をキーとして使用します。アイテムx = 1、...、nを繰り返します。 f（x）にエントリがない場合は、xを格納します。存在する場合、現在のxの値とf（x）に格納されている値は、探しているタイプのペアです。擬似コードで

：あなたはルームメイトを持ってすべてハトを特定したい場合は

h = {} # initialize an empty hashmap 
for x in 1,...,n 
    if h[f(x)] is empty 
     h[f(x)] <- x # store x in the hashmap indexed by f(x) 
    else 
     (x, h[f(x)]) qualify as a match # do what you want with them 

、空集合でハッシュマップを初期化します。次に、値を反復処理し、現在の値xをf（x）によってインデックス付けされた集合に追加します。最後に、ハッシュマップを繰り返して、複数の要素を持つすべてのセットを選択します。たとえば、次の出力を生成し

N = 10 # number of pigeons 

# Create an array of value/function pairs. 
# Using N-1 for range of rand guarantees at least one duplicate random 
# number, and with the nature of randomness, quite likely more. 
value_and_f = Array.new(N) { |index| [index, rand(N-1)]} 

h = {} # new hash 

puts "Value/function pairs..." 
p value_and_f # print the value/function pairs 

value_and_f.each do |x, key| 
    h[key] = [] unless h[key] # create an array if none exists for this key 
    h[key] << x    # append the x to the array associated with this key 
end 

puts "\nConfirm which values share function mapping" 
h.keys.each { |key| p h[key] if h[key].length > 1 } 

：

あなたはそれの楽しみのために、言語を指定しなかったので

---

私はRubyで、後者のアルゴリズムを実施することを決定しました

Value/function pairs... 
[[0, 0], [1, 3], [2, 1], [3, 6], [4, 7], [5, 4], [6, 0], [7, 1], [8, 0], [9, 3]] 

Confirm which values share function mapping 
[0, 6, 8] 
[1, 9] 
[2, 7] 

この実装ではランダム性が使用されるため、実行するたびに異なる結果が生成されます。