使用 R 解决逻辑难题

Question

我遇到了以下逻辑问题：

在此问题中，您需要将篮球运动员的真实姓名与其昵称相匹配，并按身高对篮球运动员进行排序。通常，这个问题需要你手动枚举名字-昵称和名字-身高的不同组合，直到根据下面的条件不存在矛盾为止。

我想知道是否可以使用 R 等编程语言通过暴力破解来解决此类问题。

例如，下面的代码按身高列出了篮球运动员的所有可能组合：

my_list = c("Bill", "Ernie", "Oscar", "Sammy", "Tony")

d = permn(my_list)

all_combinations  = as.data.frame(matrix(unlist(d), ncol = 120)) |>
  setNames(paste0("col", 1:120))


data_frame_version = data.frame(matrix(unlist(d), ncol = length(d))

matrix_version = matrix(unlist(d), ncol = length(d)) 

#first 20 rows of matrix version:

     [,1]    [,2]    [,3]    [,4]    [,5]    [,6]    [,7]    [,8]    [,9]    [,10]   [,11]   [,12]   [,13]   [,14]   [,15]   [,16]   [,17]   [,18]   [,19]  
[1,] "Bill"  "Bill"  "Bill"  "Bill"  "Tony"  "Tony"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Bill"  "Tony"  "Tony"  "Sammy" "Sammy" "Sammy"
[2,] "Ernie" "Ernie" "Ernie" "Tony"  "Bill"  "Bill"  "Tony"  "Ernie" "Ernie" "Ernie" "Sammy" "Sammy" "Sammy" "Tony"  "Bill"  "Sammy" "Tony"  "Bill"  "Bill" 
[3,] "Oscar" "Oscar" "Tony"  "Ernie" "Ernie" "Ernie" "Ernie" "Tony"  "Sammy" "Sammy" "Ernie" "Ernie" "Tony"  "Sammy" "Sammy" "Bill"  "Bill"  "Tony"  "Ernie"
[4,] "Sammy" "Tony"  "Oscar" "Oscar" "Oscar" "Sammy" "Sammy" "Sammy" "Tony"  "Oscar" "Oscar" "Tony"  "Ernie" "Ernie" "Ernie" "Ernie" "Ernie" "Ernie" "Tony" 
[5,] "Tony"  "Sammy" "Sammy" "Sammy" "Sammy" "Oscar" "Oscar" "Oscar" "Oscar" "Tony"  "Tony"  "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar" "Oscar"

下面的代码记录了名称-昵称的所有可能组合：

list.a <- as.list(c("Bill", "Ernie", "Oscar", "Sammy", "Tony"))

list.b <- as.list(c("Slats", "Stretch", "Tiny", "Tower", "Tree"))

result.df <- expand.grid(list.a, list.b)
result.list <- lapply(apply(result.df, 1, identity), unlist)
result.list <- result.list[order(sapply(result.list, head, 1))]

 head(result.list)
[[1]]
   Var1    Var2 
 "Bill" "Slats" 

[[2]]
     Var1      Var2 
   "Bill" "Stretch" 

[[3]]
  Var1   Var2 
"Bill" "Tiny" 

[[4]]
   Var1    Var2 
 "Bill" "Tower" 

[[5]]
  Var1   Var2 
"Bill" "Tree" 

[[6]]
   Var1    Var2 
"Ernie" "Slats" 

在我看来，这两个对象（“matrix_version”和“result.list”）应该包含这个逻辑难题的正确答案 - 我只是不知道如何从这两个对象中提取正确的组合，以便逻辑条件受到尊重。

有人可以告诉我该怎么做吗？

谢谢！

Answer 1

如果效率不是您最关心的问题，那么这里有一个非常简单的方法来暴力破解结果：只需生成所有可能的组合，然后过滤掉不满足条件的组合。

library(dplyr)

dt <- purrr::cross_df(list(
  name = list(c("Bill", "Ernie", "Oscar", "Sammy", "Tony")),
  nickname = combinat::permn(c("Slats", "Stretch", "Tiny", "Tower", "Tree")), 
  height = combinat::permn(c(6.6, 6.5, 6.3, 6.1, 6))
))

dt %>%  
  group_by(id = (seq_len(n()) - 1L) %/% 5L) %>% 
  filter(
    height[name == "Oscar"] > height[nickname == "Tree"], 
    height[nickname == "Tree"] > height[name == "Tony"], 
    height[name == "Bill"] > height[name == "Sammy"], 
    height[name == "Bill"] < height[nickname == "Slats"], 
    nickname[name == "Tony"] != "Tiny",
    height[nickname == "Stretch"] > height[name == "Oscar"], 
    height[nickname == "Stretch"] < 6.6
  )

dt看起来像这样

# A tibble: 72,000 x 3
   name  nickname height
   <chr> <chr>     <dbl>
 1 Bill  Slats       6.6
 2 Ernie Stretch     6.5
 3 Oscar Tiny        6.3
 4 Sammy Tower       6.1
 5 Tony  Tree        6  
 6 Bill  Slats       6.6
 7 Ernie Stretch     6.5
 8 Oscar Tiny        6.3
 9 Sammy Tree        6.1
10 Tony  Tower       6  
# ... with 71,990 more rows

输出是

# A tibble: 5 x 4
# Groups:   id [1]
  name  nickname height    id
  <chr> <chr>     <dbl> <int>
1 Bill  Stretch     6.5 14398
2 Ernie Slats       6.6 14398
3 Oscar Tiny        6.3 14398
4 Sammy Tree        6.1 14398
5 Tony  Tower       6   14398

Answer 2

1. 编写一个函数，将昵称转换为给定分配的名称，例如您正在测试的分配在realname <- function(nickname, i) ...哪里。i

2. 编写一个函数，将名称转换为该列表中给定分配的高度，例如该列表中的条目在height <- function(name, j) ...哪里。j

3. 根据这些函数写出 4 个条件。例如条件1是

   height("Oscar", j) > height(realname("Tree", i), j) &&
   height(realname("Tree", i), j) > height("Tony", j)
   

4. 循环for遍历所有可能的分配i并j运行所有 4 个测试。如果您发现所有测试都出来了TRUE，那么您就找到了解决方案。

编辑添加：一种稍微简单的方法：只需随机排列昵称和身高，并对每个随机选择运行测试。您可能会运行比循环更多的测试（因为您将多次测试某些配置），但覆盖所有 14400 种可能性不会花费很长时间。