// Heap's algorithm (iterative version, recursive version took waaaay longer)
// https://en.wikipedia.org/wiki/Heap%27s_algorithm

// Even though I kinda understand the algorithm, 
// *after* reading about it and converting it to JS
// I can't pretend that I came up with this solution on my own. 

const permutate = str => {	
	const lengthOfString = str.length;
	
	// split the string into an array
	const arr = str.split('');
	
	// store the results
	// initialize with the original string, save one iteration
	const results = [str];
	
	// store the "count" of each element
	// initialize with zero's eg. [0, 0, 0, 0, 0]
	// this is used to track the "stack state"  since we need to simulate the recursion
	const count = Array(lengthOfString).fill(0);
	
	let i = 1;

	while (i < lengthOfString) {
		if (count[i] < i) {

			// if i is odd, then j = count[i], else j = 0
			let j = i % 2 ? count[i] : 0;
			
			// swap the elements
			[arr[j], arr[i]] = [arr[i], arr[j]];

			// increment of the while-loop counter
			count[i] += 1;

			// simulate recursion hitting the base case
			i = 1;

			// push the result
			results.push(arr.join(''));

		} else {
			// reset the state and pop the stack by incrementing i
			count[i] = 0;
			i += 1;
		}
	}

	// remove duplicates
	return [...new Set(results)];

}

const STRING = 'abcccdef';

console.time('permutate');
const answers = permutate(STRING);
console.timeEnd('permutate');

console.log(answers);



// FOR TESTING

// if the length of the array of permutations is equal 
// to the number of possible permutations, the test passes

// Math.factorial(n) is not available in javascript
// so I used a recursive factorial function
const factorial = num => num ? factorial(num - 1) * num : 1

const frequencyOfLetters = str => str.split("").reduce((acc, cur) => (acc[cur] = acc[cur] + 1 || 1, acc), {});

const possiblePermutations = str => {
    const frequencyTable = frequencyOfLetters(str);
    const factorialOfLengthOfWord = factorial(str.length);
    const sumFactorialOfFrequencies = Object.values(frequencyTable).reduce((acc, cur) => acc * factorial(cur), 1);
    return factorialOfLengthOfWord / sumFactorialOfFrequencies;
}

const testLengthOfAnswer = (str, answersArray) => {
    if (possiblePermutations(str) === answersArray.length) {
        console.log('Test passed');
    } else {
        console.log('Test failed');
    }
}

testLengthOfAnswer(STRING, answers);