Create a gist now

Instantly share code, notes, and snippets.

@iRajul /card-sorting Secret
Created Jun 14, 2014

What would you like to do?
Card Sorting - Longest Increasing Subsequence
#include <iostream>
#include <algorithm>
#include<climits>
#include <vector>
using namespace std;
int BinarySearch(vector<int> &arr,int *small,int n, int value)
{
int low = 0;
int high = n-1;
int mid;
while (low < high)
{
mid = low + ((high - low) / 2);
//! if array's mid value is greater then search value then select
//! high as mid , this is where we are making it a ceil binary search
if (arr[small[mid]] > value)
high = mid;
else if (arr[small[mid]] < value)
low = mid + 1;
else
return mid;// found
}
return low;// not found
}
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(vector<int> &arr, int n)
{
int *small = new int[n];
int size = 0;
for(int i=0 ; i<n ;i++)
{
if(i == 0)
{
small[size] = i;
}
//! Find the "index" of the smallest element in array small, which is >=than X,
//! and change it to X. Here parent[indexOfX] = S[index - 1].
else if(arr[i] <= arr[small[size]])
{
int pos = BinarySearch(arr,small,size+1,arr[i]);
small[pos] = i;
}
//! parent[indexOfX] = Last Element Of S
else
{
size = size+1;
small[size] = i;
}
}
delete [] small;
return (size+1);
}
int matrix[4][100];
int main( )
{
int n,c;
//Get Numbers of different colors and number
cin>>c>>n;
vector<int>v(n*c);
vector<int> color;
vector<int> number;
//Get color and its corresponding number
for(int i = 0;i<n*c;i++)
{
int num,col;
cin>>col>>num;
color.push_back(col);
number.push_back(num);
}
//per is used to do permutation of given number of colors
vector<int> per;
for(int i=0; i<c; i++)
{
per.push_back(i);
}
int mini = INT_MAX;
//For each permutation we will find minimum number of moves required to
// sort array v'.
do
{
int count = 0;
for(int i=0; i<c; i++)
{
for(int j=0; j<n; j++)
{
matrix[per[i]][j] = count++;
}
}
//Generate array 'v'
for(int i=0; i<n*c; i++)
{
v[i] = matrix[color[i]-1][number[i]-1];
}
//Get minimum of all permutation in variable mini
mini = std::min(mini, (n*c) - LIS(v,n*c));
}while(next_permutation(per.begin(), per.end()));
cout<<mini;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment