Перестановки отфильтрованы без повторяющихся символов

Question

Перестановки отфильтрованы без повторяющихся символов

1

Это задача freeCodeCamp.

Моя цель - создать функцию, которая:

Принимает любую строку с любыми символами.
Создает массив со всеми возможными перестановками из этой строки.
Фильтрует массив и возвращает только строки, которые не имеют повторяющихся последовательных букв.

Возвращает число полных перестановок предоставленной строки, которые не имеют повторяющихся последовательных букв. Предположим, что все символы в предоставленной строке уникальны. Например, aab должен возвращать 2, поскольку имеет 6 полных перестановок (aab, aab, aba, aba, baa, baa), но только 2 из них (aba и aba) не имеют одинаковой буквы (в данном случае a) повторяющееся.

Я не могу понять, что я написал неправильно. Я думаю, проблема кроется либо в функции фильтра, либо в списке перестановок.

function permAlone(str) {

    if (str.length == 1) {
        return str;
    }
    // Creates all possible Permutations and pushes to an array 
    var arr = [];
    var p = 0; // position of the element which needs to be swapped
    // Loop count equal to number of Permutations.
    var loops = factorialize(str.length);
    for (var i = 0; i < loops; i++) {

        // if the position is not the last element in the strig keep swapping with next following character

        if (p != str.length - 1) {
            var splitStr = str.split('')
            arraySwapElements(splitStr, p, p + 1);
            str = splitStr.join('');
            arr.push(str);
            p += 1;
            // when position is at the last index, change position to 0
        } else {
            p = 0;
            i -= 1;
        }
    }

    // swaps 2 items in an array

    function arraySwapElements(arr, a, b) {
        var item = arr[a];
        arr[a] = arr[b];
        arr[b] = item;
    };


    // outputs a factorial of a number

    function factorialize(num) {
        if (num === 0) {
            return 1;
        } else {
            return num * factorialize(num - 1);
        }
    }

    // filters any array which has 2 or more repeating characters

    var x = arr.filter(function(str) {
        var re = /(.)\1+/;
        var result = re.test(str);
        if (!result) {
            return str;
        }
    })

    // returns the filtered arrays length
    return x.length



}

console.log(permAlone('abfdefa'));

При тестировании:

permAlone("aab") should return a number. // Correct
permAlone("aab") should return 2.  // Correct
permAlone("aaa") should return 0. // Correct
permAlone("aabb") should return 8. // Correct
permAlone("zzzzzzzz") should return 0.// Correct
permAlone("a") should return 1.// Correct
permAlone("aaab") should return 0.// Correct

permAlone("abcdefa") should return 3600. // Incorrect
permAlone("abfdefa") should return 2640.// Incorrect
permAlone("aaabb") should return 12. // Incorrect

Davis Davis 07 июнь 2017, в 15:47

Источник

Теги:

javascript

permutation

filter

1 ответ

Ещё вопросы

Matthew Lewis · Accepted Answer · 2017-08-04T11-00-00.000Z

Проблема связана с логикой, используемой в цикле for. В то время как цикл генерирует правильное количество полных перестановок, он не генерирует все перестановки.

Например, если наша строка, которая должна быть переименована, была "abcd", механизм свопинга должен генерировать строки следующим образом:

b a cd bc a d bcd a

c b да cd b a cda b

d c ab da c b dab c

a d bc ab d c abc d

О, о! Эта последняя компоновка такая же, как и начальная строка. Когда мы снова начнем замену, мы получим тот же набор, что и на первом проходе. Мы никогда не получим перестановок типа "acbd". Таким образом, результирующий массив содержит более высокие числа некоторых перестановок и меньшее количество других.

Я не уверен, как исправить это с помощью подхода, который вы используете, но рекурсивная функция для получения перестановок может быть написана следующим образом:

// Returns an array of all permutations of a string
function getPerms(str) {
  // Base case. If the string has only one element, it has only one permutation.
  if (str.length == 1) {
    return [str];
  }
  // Initialise array for storing permutations
  let permutations = [];
  // We want to find the permutations starting with each character of the string
  for (let i = 0; i < str.length; i++) {
    // Split the string to an array
    let splitStr = str.split('');
    // Pull out the character we're checking for permutations starting with
    let currentElem = splitStr.splice(i, 1)[0];
    // Get permutations of the remaining characters
    let subPerms = getPerms(splitStr.join(''));
    // Concat each of these permutations with the character we're checking
    // Add them to our list
    subPerms.forEach(function (combination) {
      permutations.push(currentElem.concat(combination));
    });
  }
  // return our list
  return combinations;
}

Нет проблем :). Я просматривал старые вопросы и подумал, что было бы интересно попытаться решить.