algorithm - 我如何解决有关鸽子原理(离散数学)的问题？

Question

我不明白下面的问题。我的意思是我想知道这个问题的示例输入输出:“鸽笼原理指出，如果函数 f 有 n 个不同的输入但少于 n 个不同的输出，则存在两个输入 a 和 b 使得 a!=b和 f(a)=f(b)。提出一个算法来找到 a 和 b，使得 f(a)=f(b)。假设函数输入为 1,2，……，和 n .?”

我无法解决这个问题，因为我没有清楚地理解这个问题。寻求您的帮助。

Answer 1

鸽巢原则说，如果你的元素多于箱子，那么至少有一个箱子必须有多个元素。

如果你想找到哪些项目 a != b 具有属性 f(a) == f(b)，一个简单的方法是使用 hashmap 数据结构。使用函数值 f(x) 作为键来存储项目值 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) 索引的集合。最后，遍历 hashmap 并挑选出所有包含一个以上元素的集合。

---

由于您没有指定语言，为了好玩，我决定在 Ruby 中实现后一种算法:

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 }

产生以下输出，例如:

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]

由于此实现使用随机性，因此每次运行它都会产生不同的结果。