如何用JavaScript实现句子单词全排列并输出所有不重复变体

• 首先放弃你现有的给单词加空格的逻辑，后续排列完成后直接用Array.prototype.join(' ')拼接成完整句子即可，灵活度更高。
• 采用回溯法生成全排列，在回溯过程中直接做重复项过滤，比全量生成后再去重的性能高很多，尤其适合有重复单词的输入场景。
• 为了方便去重判断，首先对单词数组做排序，让相同单词相邻，回溯时只要判断当前单词和前一个是否相同、且前一个未被使用，就跳过当前项，避免生成重复排列。

// 去重全排列生成函数
function permuteUnique(words) {
    const result = [];
    const used = new Array(words.length).fill(false);
    // 先排序让相同元素相邻，方便去重
    words = [...words].sort();
    
    function backtrack(current) {
        // 当前排列长度等于单词总数，拼接成句子加入结果
        if (current.length === words.length) {
            result.push(current.join(' '));
            return;
        }
        for (let i = 0; i < words.length; i++) {
            // 已经用过的单词跳过
            if (used[i]) continue;
            // 和前一个单词相同且前一个未被使用，跳过，避免重复排列
            if (i > 0 && words[i] === words[i-1] && !used[i-1]) continue;
            
            used[i] = true;
            current.push(words[i]);
            backtrack(current);
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack([]);
    return result;
}

// 测试用例
let str = "my test sentence 123";
let words = str.split(" ");
const permutations = permuteUnique(words);
console.log(permutations);
// 输出共4!=24种不重复排列，包含你示例中提到的所有组合

• 如果输入句子中有重复单词，比如输入"a a b"，函数会自动去重，只会返回3种合法不重复排列，不会生成冗余结果。
• 全排列的数量是n!（n为单词个数），如果单词个数超过10的话生成量会非常大，注意控制输入规模避免性能问题。

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