These are chat archives for camperbot/bonfire-no-repeats-please

3rd
Oct 2015 Puiyee Tong
@pytong
Oct 03 2015 01:31
hint CamperBot
@camperbot
Oct 03 2015 01:31

`hint [1/7]`

## ## :construction: After this are possible spoiler hints.

Make sure you've tried to hard to solve it yourself before proceeding. :construction:

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 01:31
hint CamperBot
@camperbot
Oct 03 2015 01:31

`hint [2/7]`

## # Problem Explanation:

• This task requires us to look at each possible permutation of a string. This is best done using a recursion function. Being able to build a function which collects all permutations of a string is a common interview question, so there is no shortage of tutorials out there on how to do this, in many different code languages.
• This task can still be daunting even after watching a tutorial. You will want to send each new use of the function 3 inputs: 1. a new string (or character array) that is being built, 2. a position in your new string that's going to be filled next, and 3. an idea of what characters (more specifically positions) from the original string have yet to be used. The pseudo code will look something like this:

``````var str = ???;
perm(current position in original string, what's been used in original string, current string build thus far){
if(current string is finished) {
print current string;
}else{
for(var i = 0; i < str.length; i++) {
if(str[i] has not been used) {
put str[i] into the current position;
mark str[i] as used
perm(current position in original string, what's been used in original string, current string build thus far)
unmark str[i] as used because another branch in the tree for i + 1 will still likely use it;
}
}
}
}
perm(0, nothing used yet, empty new string (or array the same size as str);``````
• Another way to think about this problem is to start from an empty space. Introduce the first letter to the space. This space will now contain the first sub-permutation. Here's a diagram illustrating the idea: ``````// An approach to introduce a new character to a permutation
var ch = '?';
var source = ['?', '?', '?'];     // Current sub-permutation
var temp, dest = [];

for(var i = 0; i <= source.length; ++i) {
temp = source.slice(0);    // Copy the array
temp.splice(i, 0, ch);    // Insert the new character
dest.push(temp);    // Store the new sub-permutation
}``````

Finding each permutation could then be done non-recursively by including the above in a function taking a source array and returning a destination array. For each letter of the input string, pass that character, as well as the array returned from the previous call of the function.

A way to visualize this is by considering a tree that starts with the first character of your string: type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 01:31
hint CamperBot
@camperbot
Oct 03 2015 01:31

`hint [3/7]`

## Hint: 1

• The easiest way is to use Heap's algorithm to recursively get a list of all the permutations.

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 01:58
hint CamperBot
@camperbot
Oct 03 2015 01:58

`hint [4/7]`

## Hint: 2

• Once you have the list then just create a regular expression to catch the repeating characters.

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:55
hint CamperBot
@camperbot
Oct 03 2015 14:55

`hint [1/7]`

## ## :construction: After this are possible spoiler hints.

Make sure you've tried to hard to solve it yourself before proceeding. :construction:

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:55
hint CamperBot
@camperbot
Oct 03 2015 14:55

`hint [2/7]`

## # Problem Explanation:

• This task requires us to look at each possible permutation of a string. This is best done using a recursion function. Being able to build a function which collects all permutations of a string is a common interview question, so there is no shortage of tutorials out there on how to do this, in many different code languages.
• This task can still be daunting even after watching a tutorial. You will want to send each new use of the function 3 inputs: 1. a new string (or character array) that is being built, 2. a position in your new string that's going to be filled next, and 3. an idea of what characters (more specifically positions) from the original string have yet to be used. The pseudo code will look something like this:

``````var str = ???;
perm(current position in original string, what's been used in original string, current string build thus far){
if(current string is finished) {
print current string;
}else{
for(var i = 0; i < str.length; i++) {
if(str[i] has not been used) {
put str[i] into the current position;
mark str[i] as used
perm(current position in original string, what's been used in original string, current string build thus far)
unmark str[i] as used because another branch in the tree for i + 1 will still likely use it;
}
}
}
}
perm(0, nothing used yet, empty new string (or array the same size as str);``````
• Another way to think about this problem is to start from an empty space. Introduce the first letter to the space. This space will now contain the first sub-permutation. Here's a diagram illustrating the idea: ``````// An approach to introduce a new character to a permutation
var ch = '?';
var source = ['?', '?', '?'];     // Current sub-permutation
var temp, dest = [];

for(var i = 0; i <= source.length; ++i) {
temp = source.slice(0);    // Copy the array
temp.splice(i, 0, ch);    // Insert the new character
dest.push(temp);    // Store the new sub-permutation
}``````

Finding each permutation could then be done non-recursively by including the above in a function taking a source array and returning a destination array. For each letter of the input string, pass that character, as well as the array returned from the previous call of the function.

A way to visualize this is by considering a tree that starts with the first character of your string: type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:55
hint CamperBot
@camperbot
Oct 03 2015 14:55

`hint [3/7]`

## Hint: 1

• The easiest way is to use Heap's algorithm to recursively get a list of all the permutations.

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:55
hint CamperBot
@camperbot
Oct 03 2015 14:55

`hint [4/7]`

## Hint: 2

• Once you have the list then just create a regular expression to catch the repeating characters.

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:56
hint CamperBot
@camperbot
Oct 03 2015 14:56

`hint [5/7]`

## Hint: 3

• You will want to have the permutations as an array of joined strings instead of separated characters.

type `hint` for next hint :pencil: [Contribute at the FCC Wiki] Puiyee Tong
@pytong
Oct 03 2015 14:56
hint  Puiyee Tong
@pytong
Oct 03 2015 14:59
hint CamperBot
@camperbot
Oct 03 2015 14:59

`hint [7/7]`

## Code Solution:

``````function permAlone(str) {

// Create a regex to match repeated consecutive characters.
var regex = /(.)\1+/g;

// Split the string into an array of characters.
var arr = str.split('');
var permutations = [];
var tmp;

// FUnction to swap variables' content.
function swap(index1, index2) {
tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}

//Generate arrays of permutations using the algorithm.
function generate(int) {
if (int === 1) {
// Make sure to join the characters as we create  the permutation arrays
permutations.push(arr.join(''));
} else {
for (var i = 0; i != int; ++i) {
generate(int - 1);
swap(int % 2 ? 0 : i, int - 1);
}
}
}

generate(arr.length);

// Filter the array of repeated permutations.
var filtered = permutations.filter(function(string) {
return !string.match(regex);
});

//Return how many have no repetitions.
return filtered.length;
}``````

# Code Explanation:

If you found this page useful, you can give thanks by copying and pasting this on the main chat: `thanks @Philosophist @Rafase282`
type `hint` for next hint :pencil: [Contribute at the FCC Wiki]