Ancora puzzle smemorati

[rand]

Un'altro problemino che diventa non banale se vogliamo essere efficienti in spazio:

dato un array A[1]A[2]...A[n] e un intero K sovrascrivere l'array A con il suo shift
ciclico A[k]....A[n]A[1]...A[k-1] in tempo O(n) usando come memoria solo l'array A + una quantità costante e indipendente da n di registri.

Ciao.

[SkZ]

sia k<n
se m=(n,k)

Codice: Seleziona tutto

for(j=0; j<m; j++){
  for(b=a[i=0], q=j;i<n/m-1; i++){
    p=q;
    q=(p+k)%n;
    a[p]=a[q];
  }
  a[(j+n-k)%n]=b;
}

non l'ho ancora testato
solo un'idea
a occhio vi sembra ragionevole?

EDIT: ripensando a mente non funziona (lavora troppo)

[mykelyk]

Carino, se non capite ve lo spiego:

Codice: Seleziona tutto

// testconsole.cpp : definisce il punto di ingresso dell'applicazione console.
//

#include "stdafx.h"
#include <iostream> 

using namespace std;

typedef unsigned int uint;
typedef unsigned long long uint64;
//typedef int int;
typedef long long int64;

void multishift(uint end, int* a, uint k, uint n){
	uint start, i;
	start = end + k;
	i = start;
	int first = a[i];
	while((i %= n) != end){
		a[i] = a[(i + k) % n];
		i += k;
	}
	a[end] = first;
}
void shift(int* a, uint n, uint k){
	if(n && k){
		uint min = ~0;
		uint i = k;
		while(i != min){
			if(i < min) min = i;
			i = (i + k) % n;
		}
		for(i = 0; i <= min; i++)
			multishift(i, a, k, n);
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
#define n 200
#define k 7
	int a[n];
	for(uint i = 0; i < n; i++)
		a[i] = i + 1;

	shift(a, n, k);
	
	for(uint i = 0; i < n; i++)
		cout << a[i] <<endl;
	return 0;
}

[rand]

Io avevo in mente questa soluzione. Si può vedere un qualunque shift ciclico come prodotto di 3 inversioni, dove un' inversione è una permutazione del tipo (a a+1 ... b-1 b) --> (b b-1 ... a+1 a). Poichè è facile effettuare un' inversione in loco e in tempo lineare anche lo shift ciclico viene così calcolato in loco e in tempo lineare.