Skip to content

Instantly share code, notes, and snippets.

@S2Ler
Created December 17, 2016 12:52
Show Gist options
  • Save S2Ler/bf580c391cb78268adc33ec964ff54a0 to your computer and use it in GitHub Desktop.
Save S2Ler/bf580c391cb78268adc33ec964ff54a0 to your computer and use it in GitHub Desktop.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
void permute(int *, int, int);
void permute(int *a, int n, int k) {
// reduce complexity
k = k % n;
/// special cases instant result
if (n <= 1) { return; }
if (n == k) { return; }
// store first elements
int *first_elems = calloc(k, sizeof(int));
for (int i = 0; i < k; i++) {
first_elems[i] = a[i];
}
// permute the rest
for (int i = 0; i < n - k; i++) {
a[i] = a[i+k];
}
// append first element to end
for (int i = 0; i < k; i++) {
a[n-k+i]= first_elems[i];
}
}
int main(){
int n;
int k;
scanf("%d %d",&n,&k);
int *a = malloc(sizeof(int) * n);
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
permute(a, n, k);
for (int j = 0; j < n; j++) {
printf("%d ", a[j]);
}
return 0;
}
/*
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
take k first elements
shift with override all k till n - k - 1 elements by k to left
append k first elements to end
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment