How can i adapt this code into permutating a given number of characters?

Question

I've got this kind of code:

function swap (alphabets, index1, index2) {
    var temp = alphabets[index1];
    alphabets[index1] = alphabets[index2];
    alphabets[index2] = temp;
    return alphabets;
}

function permute (alphabets, startIndex, endIndex) {
    if (startIndex === endIndex) {
        console.log(alphabets.join(''));
    } else {
        var i;
        for (i = startIndex; i <= endIndex; i++) {
            swap(alphabets, startIndex, i);
            permute(alphabets, startIndex + 1, endIndex);
            swap(alphabets, i, startIndex); // backtrack
        }
    }
}

For example if the input is [ 1, 4, 2 ] the output will be(this output is not correct) 142 142 124 124 124 142 412 412 421 421 421 412 241 241 214 214 214 241 421 412 241 214 124 142 I want this code to return a fixed amount of numbers. Example: 2characters, [ 1, 4, 2 ] => 14, 12, 42, 24, 21, 41 ; 3characters, [ 1, 4, 2 ] => 142, 124, 421, 412 and so on.

Yes that is possible. Although it might not be ideal how it is done right now with mutable lists, etc. You can simply generate permutations leaving the original list without modifications. — Willem Van Onsem, Aug 11 '19 at 13:54
I don't understand how 142 is a different permutation of 142? — MinusFour, Aug 11 '19 at 14:00
@MinusFour this code is raw and doesnt work as it meant to work like. In ideal situation it doesn't have copies in output. It's not a big problem, i can filter them out afterward — Ozkhan Mamedov, Aug 11 '19 at 14:15
Is this an answer to your question: https://stackoverflow.com/a/43260158/7778713 — D.J. Klomp, Aug 11 '19 at 15:47
@D.J.Klomp close, but i need the output number's digits to be controlable — Ozkhan Mamedov, Aug 11 '19 at 19:07

Jonas Wilms · Answer 1 · 2019-08-12T09:13:56.827

The code you currently have won't really work in the way you want it to. Instead I'd use a generator and recursion to pass up the results, and I'd pass down a copy of the alphabet down:

   function* add(iterable, value) { yield* iterable; yield value; }

   // Generates permutations of length "count" based on the "alphabet" array
   // In case count is bigger than the alphabet, the permutations will only be as big as the alphabet, elements will never be duplicated
   function* permutations(alphabet, count, previous = new Set) {
     // Base case: The wanted combination size was already reached, end here
     if(Math.max(count, alphabet.length) === previous.size) {
       yield previous;
       return;
     }

     // Otherwise go over the alphabet
     for(const value of alphabet) {
        // Skip all elements that were already added during previous recursive iterations
        if(previous.has(value)) continue;
        // Then add the current element to a new Set passed down
        yield* permutations(alphabet, count, new Set(add(previous, value)));
     }
 }

This only works under the assumption that the values are unique, so [1, 1] for example won't work. To make that work you'd have to generate an array indices, generate the permutations out of it, then map that to the values.

Usable as:

 [...permutations([1, 2, 4], 2)]

I think the last line (`yield* permutations(alphabet...`) may be missing a closing parenthesis. — גלעד ברקן, Aug 12 '19 at 02:00

score 0 · Accepted Answer · answered Aug 11 '19 at 18:29

We can adjust the permute function you've provided to accumulate copies of its results, and then apply it to combinations of the fixed length.

function swap (alphabets, index1, index2) {
    var temp = alphabets[index1];
    alphabets[index1] = alphabets[index2];
    alphabets[index2] = temp;
    return alphabets;
}

function permute (alphabets, startIndex, endIndex, result) {
    if (startIndex === endIndex) {
        result.push(alphabets.slice());
    } else {
        var i;
        for (i = startIndex; i <= endIndex; i++) {
            swap(alphabets, startIndex, i);
            permute(alphabets, startIndex + 1, endIndex, result);
            swap(alphabets, i, startIndex); // backtrack
        }
    }
    return result;
}

function combinations(A, k, i=0, acc=[]){
  if (A.length - i + acc.length == k)
    return [acc.concat(A.slice(i))]
  if (acc.length == k)
    return [acc]
  return combinations(A, k, i+1, acc.slice().concat(A[i]))
    .concat(combinations(A, k, i+1, acc))
}

function f(A, k){
  let result = []
  for (let comb of combinations(A, k))
    result = result.concat(permute(comb, 0, k - 1, []))
  return result
}

var A = [1, 2, 3]
console.log(JSON.stringify(f(A, 2)))
console.log(JSON.stringify(f(A, 3)))

How can i adapt this code into permutating a given number of characters?

2 Answers2