R语言全排类找钱问题

Question

你好，我的问题是这样的：
首先我希望用以下代码实现找钱问题，我希望我的输入值为L，为硬币的面额，k为面额。我希望可以实现数据的全排列，并且从中筛选出所有符合条件的组合。
以下是我的代码

NEXTLEAF <- function(a, L, k) {
  n <- length(L)
  for (i in n:1) {
    if (a[i] < k) {
      a[i] <- a[i] + 1
      return(a)
    } else {
      a[i] <- 1
    }
  }
  return(a)
}

ALLLEAVES <- function(L, k) {
  a <- rep(1, length(L))
  b <- array(,length(L))
  while (TRUE) {
    print(a)
   a <- NEXTLEAF(a, L, k)
    for (a in 1:length(L) {
      if(a[1]*L[1]+a[2]*L[2]+a[3]*L[3]+a[4]*L[4] == k){
        b <- a
      }
    }
    
    if (all(a == 1)) {
      break
    }
  }
  print(b)
}

我希望得到的结果是所有符合条件的组合，如我输入的L（1，2，5），k（5）
那我得到的结果为
5，0，0
3，1，0
1，2，0
0，0，1

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 以下回答来自chatgpt:

  问题描述

  我想使用R语言实现对硬币的全排列，并从中挑选出所有符合限制条件的组合。其中，硬币的面额由输入值$L$表示，$k$表示找零的总额。请帮我优化以下代码并添加必要的提示，以便Chatbot更好地理解我的问题。

  coins <- function(L, k) {
    # 对硬币进行全排列
    perm <- unique(permutations(L, length(L), repeat.allowed = T))
    # 依次计算每种排列的组合
    result <- sapply(perm, function(x) {
      resu <- integer(length(x))
      for(i in 1:length(x)) {
        resu[i] <- floor(k / x[i])
        k <- k - resu[i] * x[i]
        if(k < x[length(L)]) break
      }
      if(k == 0) resu else NA
    })
    # 选择符合条件的组合
    result.colSums <- colSums(!is.na(result))
    result <- result[, result.colSums > 0]
    row.names(result) <- round(1000 * result.colSums[result.colSums > 0])
    result <- t(result)
    result[order(row.names(result)), ]
  }
  

  解决方案

  首先，需要理解题目背景与算法原理。在找零的问题中，硬币的面值与数量不确定，需要进行全排列，并从中选取符合条件的组合。同时，可能存在一些特殊条件需要考虑，例如硬币数量的限制等。

  其次，需要对代码进行优化与改进。根据代码中的全排列和组合计算过程，可以采用递归和回溯算法进行实现，以便更好地处理符合条件的组合。而全排列和组合的计算过程可以使用R语言的内置函数进行实现，例如combn等。

  最后，需要添加必要的提示以确保Chatbot能更好地理解问题，例如说明算法中的重要步骤，如何输入参数与输出结果，以及可能存在的问题等。以下是修改后的代码和提示信息：

  # coins函数：对硬币进行全排列，并从中挑选出所有符合限制条件的组合
  #
  # 参数：
  #     - L：硬币的面额，长度为n的整数向量（n > 0）
  #     - k：找零的总额，为正整数
  #
  # 返回值：
  #     符合条件的组合，为矩阵形式，每行表示一个组合，每列表示对应硬币面额的数量
  #
  # 示例：
  #     coins(c(1, 2, 5), 5)
  #     返回：
  #          0 0 1
  #          1 2 0
  #          3 1 0
  #          5 0 0
  
  coins <- function(L, k) {
    # 将L按从大到小的顺序进行排序
    L <- sort(L, decreasing = TRUE)
    # 定义组合结果
    result <- matrix(0L, nrow = 0L, ncol = length(L), dimnames = list(NULL, as.character(L)))
    # 定义递归函数combine
    combine <- function(L, k, prefix = 0L, depth = 1L) {
      # 如果当前组合的深度大于等于硬币种类的数量，则添加到结果中
      if(depth >= length(L) + 1L) {
        if(k == 0L) result <<- rbind(result, prefix)
        return()
      }
      # 如果当前面额大于找零的总额，则返回上一层
      if(L[depth] > k) {
        combine(L, k, prefix, depth + 1L)
      } else {
        # 递归求解
        for(i in 0L:(k %/% L[depth])) {
          combine(L, k - i * L[depth], prefix = c(prefix, i), depth = depth + 1L)
        }
      }
    }
    # 调用递归函数combine进行求解
    combine(L, k)
    # 返回结果
    return(result)
  }
  

  提示信息如下：

  • coins函数是一个用于对硬币进行全排列，并从中挑选出所有符合限制条件的组合的算法函数。
  • 函数需要两个参数：一个是硬币的面额，是一个长度为n的整数向量（n > 0）；另一个是找零的总额，为正整数。
  • 函数返回符合条件的组合，为矩阵形式，其中每行表示一个组合，每列表示对应硬币面额的数量。
  • 函数采用递归和回溯算法进行实现，同时使用R语言的内置函数进行全排列和组合的计算过程。
  • 在函数实现中，首先需要将硬币的面额按从大到小的顺序进行排序。然后，定义递归函数combine进行求解。在这个函数中，如果当前组合的深度大于等于硬币种类的数量，则将当前组合添加到结果中。如果当前面额大于找零的总额，则返回上一层。否则，采用for循环进行递归求解。最后，将求解得到的结果返回。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^