基于指定字符顺序的可变长度字符串字典序排序问题

我已成功生成1到n长度的所有字符可重复排列，但需要实现按指定字符顺序的自定义字典序排序。例如输入字符为D N A时，需遵循D优先于N、N优先于A的规则排序，n=3时共生成39种排列。

以下是当前生成排列的代码，核心问题是如何添加自定义排序逻辑：

text_input <- c("D", "N", "A")
n <- 3

empty_df <- data.frame(matrix("", ncol = n))

temp_df <- data.frame()

for (i in n:1) {
  temp_df <- data.frame(arrangements::permutations(text_input, k = i, replace = TRUE))
  empty_df <- bind_rows(empty_df, temp_df)
}

result_df <- replace(empty_df, is.na(empty_df), "") |>
  unite(col = combined, everything(), sep = "", remove = FALSE) |>
  mutate(across(2:(n+2), ~ factor(.x, levels = text_input)),
         across(2:(n+2), ~ str_replace_na(.x, replacement = "")))

result_vec <- tail(result_df$combined, -1)

解决方案：自定义字典序排序 #

这里提供两种可行的排序实现方式，核心都是基于指定字符顺序生成权重，以此为依据排序：

方法1：基于因子权重的DataFrame排序

直接在现有DataFrame中生成排序键，利用dplyr::arrange完成排序：

library(arrangements)
library(dplyr)
library(stringr)

text_input <- c("D", "N", "A")
n <- 3

empty_df <- data.frame(matrix("", ncol = n))
temp_df <- data.frame()

for (i in n:1) {
  temp_df <- data.frame(arrangements::permutations(text_input, k = i, replace = TRUE))
  empty_df <- bind_rows(empty_df, temp_df)
}

result_df <- replace(empty_df, is.na(empty_df), "") |>
  unite(col = combined, everything(), sep = "", remove = FALSE) |>
  # 生成排序键：将字符串拆为字符，转换为指定顺序的因子并取数值
  mutate(sort_key = lapply(str_split(combined, ""), function(chars) {
    as.numeric(factor(chars, levels = text_input))
  }))

# 按自定义排序键排序，提取结果
sorted_result <- result_df %>%
  arrange(sort_key) %>%
  pull(combined) %>%
  tail(-1) # 移除初始空行

# 查看排序后结果
cat(paste(sorted_result, collapse = "\n"))

方法2：独立向量排序

如果已经有了result_vec，可以通过字符权重映射直接排序：

# 构建字符到权重的映射（顺序对应指定优先级）
char_weights <- setNames(seq_along(text_input), text_input)

# 定义函数：将字符串转换为权重序列
get_sort_key <- function(str) {
  sapply(str_split(str, "")[[1]], function(c) char_weights[[c]])
}

# 对结果向量排序
sorted_result <- result_vec[order(sapply(result_vec, get_sort_key))]

# 输出结果
cat(paste(sorted_result, collapse = "\n"))

两种方法的原理一致：将每个字符映射到指定顺序的数值权重，排序时优先比较字符串的第一个字符权重，依次往后；短字符串会自然排在前缀相同的长字符串之前（例如D排在DD之前），完全符合题目要求的自定义字典序规则。

内容的提问来源于stack exchange，提问作者Godrim