CareerCup

Arrange the array in descending order for eg n=4
4,3,2,1
(rotate the array 3 times i.e length(array)-1
3,2,1,4
2,1,4,3
1,4,3,2

Note leave the first element from (4,3,2,1) i.e take 3,2,1 (rotate the array 2 times i.e length(array)-1
4,2,1,3
4,1,3,2

Note leave the 2 elements from (4,3,2,1) i.e take 2,1 (rotate the array 1 times i.e length(remainingarray)-1

4,3,1,2

I think this should work

void special_perm(int *a, int ai, int len)
{
	int i;

	if(len == 0) {
		print_arr(a, ai);
		return;
	}
		
	for(i=0; i<len; i++) {
		if(ai == 0 || a[ai-1] +1 != a[ai+i]) {
			swap(a, ai, ai+i);
			special_perm(a, ai+1, len-1);
			swap(a, ai, ai+i);
		}
	}
}

int a[] = {1,2,3,4};
special_perm(a, 0, 4);

How about this solution in Scala?

object Main {

  def insert(x: Int, items: List[Int]): List[List[Int]] = {
    if (items isEmpty) List(List(x))
    else for {
      i <- (0 to items.length).toList
      val s = items.splitAt(i) 
    } yield s._1 ::: (x :: s._2)    
  }
      
  def perms(a: List[Int]): List[List[Int]] = a match {
    case Nil => List(List())
    case x :: xs => for {
      p <- perms(xs)
      i <- insert(x, p)
    } yield i      
  }

  def special(items: List[Int]): Boolean = items match {
    case Nil => true
    case x :: xs => xs match {
      case Nil => true
      case y :: ys => x != y - 1 && special(xs)
    }
  }
  
  def main(args: Array[String]) {
    val items = List(1, 2, 3, 4)
    println(perms(items))
    println(perms(items).filter(special))    
  }

}

It simply filters from all possible permutations

Sol 1: create a circular array and print all elements of it and keep shifting the first index.

Sol 2: or create a string and every time eliminate front char and add it in last and print the complete string.

can any one explain the Question in details

a general backtrack in c++

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void print(vector<int> v){
	for(int i = 0; i < v.size(); ++i )
		cout<<v[i]<<" ";
	cout<<endl;
}

bool isSolution(vector<int> s, int step, int n){
	return step == n;
}

void processSolution(vector<int> s, int step, int n){
	print(s);
}

void generateSpace(vector<int> s, int step, int n, vector<int> &space){
	vector<int>::iterator sBegin = s.begin();
	vector<int>::iterator sEnd = s.end();
	int key = -1;
	if(s.size()>0)
		key = s.back();			// s.back() is unstable when s is empty
	for(int i=1; i <=n; i++){
		if( find(sBegin,sEnd, i) == sEnd and i != key-1)
			space.push_back(i);
	}
}


void backtrack(vector<int> s, int step, int n){
	if( isSolution( s, step, n) ){
		processSolution(s,step,n);
	}
	else{
		++step;
		vector<int> space;
		generateSpace(s,step,n,space);
		for(int i = 0;i < space.size(); i++){
			s.push_back( space[i] );
			backtrack(s,step,n);
			s.erase(s.end()-1);
		}

	}
}

int main(){
	vector<int> s;
	int step = 0;
	int n = 3;
	backtrack(s,step,n);

	return 0;
}

A good permutation is composed by pulling out an element from the list and then finding all "good" permutations of the remaining elements that don't begin with the pulled out element's successor. This is fairly easy to code up recursively, and the recursive solution prunes bad permutations effectively. A more naive solution would be to just generate all permutations and filter out bad permutations.

def good_permute(arr, bad_head = None):
    if len(arr) == 1:
        if arr[0] == bad_head:
            return []
        return [arr]
    result = []
    for i in range(len(arr)):
        v = arr[i]
        if v == bad_head: continue
        others = arr[:i] + arr[i+1:]
        for p2 in good_permute(others, v+1):
            result.append([v] + p2)
    return result

print good_permute([1,2,3,4])

i need java code and complete explanation of this problem

int a[][4];//source array
int b[4]={4,3,2,1}
int i=0;//global value
for(int j=0;j<4;j++)//first array reverse
{
a[i][j]=b[j];

}
i++;

1 //first four elemnts shifting
for( ;i<4;i++)
{
for(int j=0,k=1;j<4;j++)
{
if(K==4)
k=0;
else{
a[i][j]=a[i-1][k];
k++;
}
}
}
2 //Right element constant remaing all element rotate two times
int f=i,k=0;
for(int a=0;a<2;a++)//this two time rotaion
{
if(a==0)
{
k=0;
}
else
k=f; //second time k value will last for i value
for(;k<4;k++)
{
for(int z=0;z<=4;z++)
{
if(z==0)
a[i][j]=a[k][z];
//last three are rotation
if(z==4)
z=0;

a[i][j]=a[k][z+1];
j++;
}
i++;
}
}
3 //left elemenmt constant remaing first three are one time rotation
for(int x=0;x<4;x++)
{ j=0;
for(int y=0;y<=3;y++)
{
if(y==3)
y=0;
a[i][j]=a[x][y+1];
j++;
}
a[i][j]=a[x][3];
i++;
}
}

o/p:explation workin of this
first rotation
4321 3214 2143 1432
second:right one constant remaing two times rotaion (rotation done obn the first four only if done on remaing same one will come again and again)
4213 3142 2431 1324
4132 3421 2314 1243
third :left one is constant remaing all (first three) rotaion
3241 2134 1432 4321

need java code for that