CareerCup

public static void main(String args[]){
        System.out.println(count("12345"));
    }
    public static int count(String str){
        int n = str.length();
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

Can be solved using recursion. For each element there arises two choices:
1. Leave the current. Permute rest of array.
2. Swap current with next. Permute rest of array starting from next's next. as both these cannot be used.

Sample code:

private void permutate(char[] a, int start, ArrayList<char[]> r){
		if(start >= a.length){
			//Base case
			r.add(a.clone());
			return;
		}
		else {				
			//Leave current and permutate rest.
				permutate(a, start+1, r);
				
			//Swap current with next and permutate leaving these two.
			if(start+1 < a.length) {// check needed if it is lonely else will go out of bound.
				swap(a, start, start+1);
				permutate(a, start+2, r);
				swap(a, start, start+1);
			}
		}
	}

int arr[] = { 1, 2, 3, 4, 5};
    
    System.out.println(perm(arr)); //7 + the original 
   }
   
   public static int perm(int arr[]){
     int n=arr.length;
     int count =0;
     for (int i=0; i<n-1;i++){
       swap(arr[i],arr[i+1]);
       count++;
       for (int j=i+2;j<n-1;j++){
            swap(arr[j],arr[j+1]);
            count++;
       }
     }
     return count;
   }
   
   public static void swap(int a, int b){
     int s = a;
     a = b;
     b = s;

  }

public class AdjPerm {
	
	private static String word = "12345"; //I assume the consecutive characters are not the same
	
	public static void main(String[] args) {
		System.out.println(adj(word.length())); //8
	}
	
	public static int adj(int i) { //Returns the number of permutations
		if (i == 0) return 1;
		else if (i < 0) return 0;
		
		return adj(i - 1) + adj(i - 2);
	}
}

What if adjacent numbers are same? Like {1,2,2}

I think the solution is Fibonacci sequence...

Solution in Python:

def numOfSwapPermutations(word):
    if len(word) == 0:
        return 1
    if len(word) == 1:
        return 1
    if len(word) > 1:
        return numOfSwapPermutations(word[:-1]) + numOfSwapPermutations(word[:-2])

a) shall we only create distinct permutation? e.g. from "aaaa" -> 1, from "aab", 2
b) in the sample the first element "2" is actually swapped twice:
12345
*2*1345, swapped 2 with 1
13*2*45, swapped 2 with 3
thus I conclude the task is to only swap an element once per permutation

as a result the recursion would look like

curly brackets "{}" indicate the optional conditions if only distinct permutations shall be created.

dp(i) = 0, if i < 0
	= 1, if i == 0
	= dp(i-1) {if dp[i] == dp[i-1]}		
	= dp(i-2) + 1 + dp(i-1) - 1 {if dp[i] != dp[i-1]} ==> dp(i-2) + dp(i-1)

reasoning
dp(i) = dp(i-2) + 1: if the elements are different they can be swapped thus extending the dp(i-2) with one option. This path count's e.g. "(123)+54" and "(123)+45"
dp(i) = dp(i-1) - 1: this counts "(1234)+5" but because "(1234)+5" = (123)+45" I have to remove one permutation, because I already counted that with (123)+45

@kustav.adorable: I think that answers your question, too, right?

Solution in Python/3.6.1 for the number of permutations and all the permutations, using expanding list and two helper lists:

import sys

def get_permutations(result, map_, done, length, target):
	i = 0
	while map_[target].find('FF', i) >= 0:
		index = map_[target].index('FF', i)
		new_permutation_map = list(map_[target])
		new_permutation_map[index] = 'T'
		new_permutation_map[index + 1] = 'T'
		new_permutation_map = "".join(new_permutation_map)
		new_permutation = list(result[target])
		new_permutation[index] = list(result[target])[index+1]
		new_permutation[index+1] = list(result[target])[index]
		new_permutation = "".join(new_permutation)
		if new_permutation not in result:
			result.append(new_permutation)
			map_.append(new_permutation_map)
			done.append(False)
		i = index + 1
	done[target] = True

def get_all_permutations(in_):
	result = [in_]
	length = len(in_)
	map_ = ['F' * length]
	done = [False]
	while(not all(done)):
		target = done.index(False)
		get_permutations(result, map_, done, length, target)
	print('#Permutations: ' + str(len(result)))
	print('Permutations: ' + str(result))

if __name__ == '__main__':
	get_all_permutations('12345')
	get_all_permutations('abcdefgh')

Solution in Python/3.6.1 for the number of permutations and all permutations using expanding list and two helper lists:

import sys

def get_permutations(result, map_, done, length, target):
	i = 0
	while map_[target].find('FF', i) >= 0:
		index = map_[target].index('FF', i)
		new_permutation_map = list(map_[target])
		new_permutation_map[index] = 'T'
		new_permutation_map[index + 1] = 'T'
		new_permutation_map = "".join(new_permutation_map)
		new_permutation = list(result[target])
		new_permutation[index] = list(result[target])[index+1]
		new_permutation[index+1] = list(result[target])[index]
		new_permutation = "".join(new_permutation)
		if new_permutation not in result:
			result.append(new_permutation)
			map_.append(new_permutation_map)
			done.append(False)
		i = index + 1
	done[target] = True

def get_all_permutations(in_):
	result = [in_]
	length = len(in_)
	map_ = ['F' * length]
	done = [False]
	while(not all(done)):
		target = done.index(False)
		get_permutations(result, map_, done, length, target)
	print('#Permutations: ' + str(len(result)))
	print('Permutations: ' + str(result))

if __name__ == '__main__':
	get_all_permutations('12345')
	get_all_permutations('abcdefgh')

Solution in Python/3.6.1 for the number of permutations and the permutations using growing list and two helpers.

def get_permutations(result, map_, done, length, target):
	i = 0
	while map_[target].find('FF', i) >= 0:
		index = map_[target].index('FF', i)
		new_permutation_map = list(map_[target])
		new_permutation_map[index] = 'T'
		new_permutation_map[index + 1] = 'T'
		new_permutation_map = "".join(new_permutation_map)
		new_permutation = list(result[target])
		new_permutation[index] = list(result[target])[index+1]
		new_permutation[index+1] = list(result[target])[index]
		new_permutation = "".join(new_permutation)
		if new_permutation not in result:
			result.append(new_permutation)
			map_.append(new_permutation_map)
			done.append(False)
		i = index + 1
	done[target] = True

def get_all_permutations(in_):
	result = [in_]
	length = len(in_)
	map_ = ['F' * length]
	done = [False]
	while(not all(done)):
		target = done.index(False)
		get_permutations(result, map_, done, length, target)
	print('#Permutations: ' + str(len(result)))
	print('Permutations: ' + str(result))

if __name__ == '__main__':
	get_all_permutations('12345')
	get_all_permutations('abcdefgh')

Solution in Python/3.6.1 for number of permutations and the permutations using a growing list and two helper lists.

def get_permutations(result, map_, done, length, target):
	i = 0
	while map_[target].find('FF', i) >= 0:
		index = map_[target].index('FF', i)
		new_permutation_map = list(map_[target])
		new_permutation_map[index] = 'T'
		new_permutation_map[index + 1] = 'T'
		new_permutation_map = "".join(new_permutation_map)
		new_permutation = list(result[target])
		new_permutation[index] = list(result[target])[index+1]
		new_permutation[index+1] = list(result[target])[index]
		new_permutation = "".join(new_permutation)
		if new_permutation not in result:
			result.append(new_permutation)
			map_.append(new_permutation_map)
			done.append(False)
		i = index + 1
	done[target] = True

def get_all_permutations(in_):
	result = [in_]
	length = len(in_)
	map_ = ['F' * length]
	done = [False]
	while(not all(done)):
		target = done.index(False)
		get_permutations(result, map_, done, length, target)
	print('#Permutations: ' + str(len(result)))
	print('Permutations: ' + str(result))

if __name__ == '__main__':
	get_all_permutations('12345')
	get_all_permutations('abcdefgh')

dp = [0 for _ in xrange(N+1)]
dp[0] = 1
dp[1] = 1
for i in xrange(2, N+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[N]

Solution in javascript with recursion:

const generatePermutations = (str, pos = 0) => {
  let arr = [str];
  for(let i = pos; i < str.length-1; i++) {
    arr = arr.concat(
      generatePermutations(swap(str, i, i+1), i+2)
    );
  }
  return arr;
}

need to find ony number of poss perm
Answer: (2^n-1)

@sudip.innovates or @cemaivaz

Can you please explain how does the problem boil down to dp[i-1]+dp[i-2]?