C# - Všechny variace k-té třídy z n prvků

[Xmat 566]

Zdravím,

 

řeším v C# jednu úlohu a zarazil jsem se na tomhle problému. Potřebuju udělat výčet všech k členných variací z n prvků, s možným opakováním.

 

Příklad, prvky a,b,c, a potřebuji výčet: aa,ab,ac,ba,bb,bc,ca,cb,cc

 

Teotericky vzato bych to dokázal udělat přes milion cyklů a counterů, ale potřebuji na to nějaký jednoznačný algoritmus, protože n a k té variace se bude měnit, protože jak členů tak prvků bude asi celkem dost a ne jen pár.

 

Předem díky

[bLuma 225]

dokud není poslední variace {
 nastav "pozici" na poslední prvek;
 dokud {
   inkrementuj prvky[pozici] (s případným přetečením na první prvek ze seznamu)
   nastav pozici na předchozí prvek
 } (prvky[pozice+1] == první prvek ze seznamu)

 yield(prvky);
}

 

Mám prvky 0,1, tučně značím co projde na yield. Začnu s variací 000 (tu je nutné ošetřit samostatně, psal jsem triviální algoritmus). Inkrementuju poslední 001. Inkrementuju poslední (přeteče) 000, uplatní se vnitřní cyklus a inkrementuji druhou pozici 010. Inkrementuji poslední 011. Inkrementuji poslední (přeteče) 010, posunu se, inkrementuji (přeteče) 000, posunu se, 100. Atd...

 

Pokud si to napíšeš dostatečně obecně dá se to použít na znaky (string) i velké rozsahy čehokoliv (pole).

Edited July 14, 2011 by bLuma

[SneakerXZ 547]

Ještě mě napadá řešení, kde by sis spočítal počet variaci a potom vytvořil pole o takové velikosti a rekurzivně bys lepil znaky.

[Xmat 566]

No, z tého bLumova jsem mírně na větvi, ale nějak se skrz to proderu, díkes.

[Wolf Officious 1382]

Kdyby šlo o C++ (a jsem si vědom toho že o c++ tu nejde), tak bych to udělal asi takhle (ale je to statický):

(po rozmluvě na skype už vím o co ti jde, takže..)

 

/* ========================================= *
*          (c) 2011 Wolf Officious          *
* ========================================= */

#include <string>
#include <iostream>
#include <tchar.h>
#include <stdio.h>

using namespace std;

// Definitions
#define CHAR_MAXIMAL    36
#define CH_Z            (CHAR_MAXIMAL - 1)

// Global vars
int code[5]            = {   0,    0,    0,    0,    0};
static int code_end[5] = {CH_Z, CH_Z, CH_Z, CH_Z, CH_Z};

char characters[CHAR_MAXIMAL] = {'0','1','2','3','4','5','6','7','8','9',
                                'a','b','c','d','e','f','g','h','i','j',
                                'k','l','m','n','o','p','q','r','s','t',
                                'u','v','w','x','y','z'};
// fce Prototypes
bool CODE_iterator();
string CODE_translate(int code_to_trans[5]);

// MAIN fce
int _tmain(int argc, _TCHAR* argv[])
{
   cout << endl
        << "START AT: " << CODE_translate(code)     << endl
        << " STOP AT: " << CODE_translate(code_end) << endl
        << endl;

   while(1)
   {
       // DEBUG - vypis aktualni hodnoty
       cout << CODE_translate(code) << endl;

       // TODO: zbytek kodu

       if(!CODE_iterator())
           break;
   }

   cout << endl << "Hotovo...";
   return 0;
}

bool CODE_iterator()
{
   int check = 0;

   for(int i = 4; i >= 0; --i)
   {
       if(code[i] == code_end[i])
       {
           ++check;
       }

       if(code[i] == CH_Z)
       {
           code[i] = 0;
           continue;
       }
       else
       {
           ++code[i];
           break;
       }
   }

   if(check >= 5)
       return false;

   return true;
}

string CODE_translate(int code_to_trans[5])
{
   string out;

   out  = characters[code_to_trans[0]];
   out += characters[code_to_trans[1]];
   out += characters[code_to_trans[2]];
   out += characters[code_to_trans[3]];
   out += characters[code_to_trans[4]];

   return out;
}

 

Edited July 14, 2011 by Wolf Officious