Vector blockweise mischen

Hey,

ich möchte einen std::vector gerne blockweise mischen. Das heißt, dass nicht der gesamte Vector gemischt wird, sondern immer nur ein Teil davon. Momentan habe ich das so gelöst, aber die Lösung sagt mir nicht so zu.

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>

typedef std::vector<int> Vec;

void fillVec(Vec& v, unsigned int count);
void partialShuffle(Vec& v, unsigned int blockSize);

int main()
{
	Vec v;

	srand(static_cast<unsigned int>(time(NULL)));

	for (unsigned int i = 0; i < 25; ++i)
	{
		fillVec(v, 15);

		partialShuffle(v, 4);

		for (unsigned int j = 0; j < v.size(); ++j)
		{
			std::cout << v[j] << " ";
			if ((j+1) % 4 == 0 && j > 0) std::cout << " | ";
		}

		std::cout << " = " << v.size() << std::endl;
	}
}

void fillVec(Vec& v, unsigned int count)
{
	v.clear();

	for (unsigned int i = 1; i <= count; ++i)
	{
		v.push_back(i);
	}
}

void partialShuffle(Vec& v, unsigned int blockSize)
{
	Vec block, res;

	if (blockSize <= 0)
	{
		return;
	}

	for (unsigned int i = 0; i < v.size();)
	{
		for (unsigned int j = 0; j <= blockSize - 1 && i < v.size(); ++j, ++i)
		{
			block.push_back(v[i]);
		}

		std::random_shuffle(block.begin(), block.end());
		res.insert(res.end(), block.begin(), block.end());

		block.clear();
	}

	v = res;
}

Geht es einfacher und schöner?

SeppJ

Wozu selber machen, was schon in der Standardbibliothek ist?

Blockweises Mischen

edit: Ups, du hast random_shuffle ja schon benutzt. Warum denn dann so kompliziert und nicht einfach auf den zu mischenden Block anwenden?

Dravere

@SeppJ,
Er benutzt ja schon random_shuffle nur unheimlich umständlich.

void partial_shuffle(std::vector<int>& vec, std::size_t blockSize)
{
  if(blockSize == 0)
  {
    return;
  }

  if(blockSize == 1)
  {
    std::random_shuffle(vec.begin(), vec.end());
  }

  std::size_t vecSize = vec.size();
  std::vector<int>::iterator first = vec.begin();

  while(vecSize >= blockSize)
  {
    std::vector<int>::iterator last = first;
    std::advance(last, blockSize);

    std::random_shuffle(first, last);

    first = last;
    vecSize -= blockSize;
  }

  std::random_shuffle(first, vec.end());
}

Ungetestet, einfach schnell aus dem Kopf raus.

Grüssli

Dravere schrieb:

void partial_shuffle(std::vector<int>& vec, std::size_t blockSize)
{
  if(blockSize == 0)
  {
    return;
  }
  
  if(blockSize == 1)
  {
    std::random_shuffle(vec.begin(), vec.end());
  }

Bei blockSize==1 gibt's aber nichts zu tun. Du machst aus blockSize==1 einfach blockSize==vec.size().

kk

Dravere

krümelkacker schrieb:

Bei blockSize==1 gibt's aber nichts zu tun. Du machst aus blockSize==1 einfach blockSize==vec.size().

Jap, stimmt. Denkfehler gemacht. War wie gesagt, ganz schnell hingeschrieben. Sonstige Fehler?

Grüssli

Danke für eure Antworten. Was haltet ihr von meiner neuen Lösung:

void partialShuffle(Vec& v, unsigned int blockSize)
{
   if (blockSize <= 1)
   {
	   return;
   }

   int limit = (v.size() - (v.size() % blockSize)) / blockSize;

   for (Vec::iterator it = v.begin(); it != v.end(); --limit)
   {
	   std::random_shuffle(it, it + blockSize);

	   it += blockSize;

	   if (limit <= 1)
	   {
		   blockSize = v.size() % blockSize;
	   }
   }
}

Müsste doch korrekt sein, oder?

volkard

Version von Dravere ein wenig verändert (ungetestet):

void partial_shuffle(std::vector<int>& vec, std::size_t blockSize)
{
  std::vector<int> shuffledEnd=vec.begin();
  while(std::size_t toDo=std::min(vec.end()-shuffledEnd,blocksize))
  {
    std::random_shuffle(shuffledEnd,shuffledEnd+toDo);
    shuffledEnd+=toDo;
  }
}

unskilled

In der 3. Zeile fehlt noch nen ::iterator

bb