javascript - 使用递归、Ramda.js 和无点风格重构字符串的 getPermutations()

Question

这个问题已经有答案了:

Permutation Javascript (3 个回答)

已关闭 7 年前。

我一直在尝试使用 Ramda.js 使用无点方法将原始解决方案重构为 getPermutations() 函数。是否可以进一步将其重构为无点风格。看来我刚刚惹出了更大的麻烦。另外，当前运行测试时，重构版本中存在一个错误:TypeError:reduce:list必须是数组或可迭代。

原始解决方案:

// getPermutations :: String -> [String]
function getPermutations(string) {
  function permute(combination, permutations, s) {
    if (!s.length) {
      return permutations[combination] = true;
    }

    for (var i = 0; i < s.length; i++) {
      permute( combination.concat(s[i])
             , permutations
             , (s.slice(0, i) + s.slice(i+1))
             );
    }
    return Object.keys(permutations);
  }

  return permute('', {}, string);
}

我尝试使用 Ramda.js 进行重构:

var _ = require('ramda');

// permute :: String -> {String: Boolean} -> String -> [String]
var permute = _.curry(function (combination, permutations, string) {
  // callPermute :: String -> ({String: Bool} -> Char -> Int -> String) -> IO
  var callPermute = function (combination) {
    return function (acc, item, i, s) {
      return permute( _.concat(combination, item)
                    , acc
                    , _.concat(_.slice(0, i, s), _.slice(i + Infinity, s))
                    );
    };
  };

  var storeCombination = function () { 
    return permutations[combination] = true;
  };

  // should be an ifElse, incorporating compose below
  _.when(_.not(string.length), storeCombination);

  return _.compose( _.keys
                  , _.addIndex(_.reduce(callPermute(''), {}))
                  ) (string.split(''));
});

// getPermutations :: String -> [String]
var getPermutations = permute('', {});

Answer 1

您的解决方案似乎有几个问题，恐怕我没有时间追查它们。 (我看到的第一件事是您错误地使用了 addIndex。)

但是如果您想在 Ramda 中查看有效的排列函数，I wrote this不久前:

// permutations :: [a] -> [[a]]
const permutations = (tokens, subperms = [[]]) =>
  R.isEmpty(tokens) ?
    subperms :
    R.addIndex(R.chain)((token, idx) => permutations(
      R.remove(idx, 1, tokens), 
      R.map(R.append(token), subperms)
    ), tokens);

R.map(R.join(''), permutations(['A', 'B', 'C'])); 
//=> ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

(您可以在 Ramda REPL 上玩这个。)