Algoritmus pro generování znaků

25.6.2007 15:28 | Přečteno: 3787× | poslední úprava: 25.6.2007 18:34

Ahoj, narazil jsem na problémek se sestavením algoritmu pro generování náhodných znaků. Ne nejedná se o domácí úkol nebo podobně. Zadání tohoto příkladu bylo u zkoušky z programování v pascalu. Přiznávám trochu jsem se do toho zamotal. Takže zadání bylo následující: Generuj náhodný počet náhodných znaků v rozmezí 150 až 250 znaků z množiny čísel 0 až 9 a velkých a malých písmen anglické abecedy. Generované znaky musí být v poměru zadaném uživatelem. Tz. např. 30% znaků čísel. Generované znaky zapiš do souboru a to náhodně. Nešlo tedy vygeneroval 30% znaků čísel zapsat do souboru a dogenerovat znaky písmen do 100% celkového počtu znaků. Výsledkem měl být soubor, kde bude např. celkem 100 znaků, z toho 30 znaků čísel a 70 znaků velkých a malých písmen.

Ideu jak to udělat jsem měl, ale .... Případ kdy je 100 nebo 0 procent čísel je v pořádku. Problém mám kdy je to mezi Myslel jsem něco jako

pom:=random(2);
if (pom=0) then ............... "generuj cislo";
   else
    if pom(1) then 
     begin 
       pom:=random(2);
       if (pom:=0) then ....... "generuj male pismeno"
        else .................. "generuj velke pismeno"
     end;

celé to zaobalit do for i:=1 to celkovy_pocet_znaku. Jenze se mi nějak nedaří dostat tam tu podmínku dodržení procent znaku/cisel. Podařilo se mi, že podmínka byla dodržena, ale měl jsem o 1 nebo 2 znaky více, nebo mi seděl celkový počet znaků, ale neseděli procenta. Nemáte někdo nějaký nápad jak z toho? Pro tu zkoušku to už není podstatné, jen mi to leží v hlavě

       

Komentáře

[kaaja]

Záleží co se myslí větičkou
Generované znaky musí být v poměru zadaném uživatelem.
Může se tím myslet, že znaků musí být přesně v daném poměru (ale to lze jenom při správném počtu znaků), nebo mají být generovány s pravděpodobnostmi v tom poměru (tady by se skutečný poměr měl přibližovat k zadanému s rostoucím počtem čísel).

[Radek Trnka]

Mám to osetrene tak, ze zaokrouhluje na cela cisla. takze vypocitám a zaokrouhlim pocet cisel. Pismana=celkovy_pocet-cisel.

[miso]

gemerator by si mal najst tu

[stativ]

Nejspíš bych nejdřív použil generátor náhodných čísel a pak bych do for smyčky dal if podmínky, kde v případě, že by vygenerované číslo bylo sudé, tak by to pokračovalo generováním čísla, když by bylo liché, tak čísla. Zároveň bych do obou podmínek dal nějakou bool proměnou, která by určovala, jestli už je jich vygenerováno dostatek. Když by jich bylo dost, generování by se pro daný typ ukončilo.

[stativ]

Rychla ukazka:

short cisel = 0.3; // 30% tohle at se vsechno nastavi nekde na vstupu
short pismen = 0.7; // 70%
int celkem = 100;

int celkem_cisel = celkem*cisel;
int celkem_pismen = celkem*pismen;

for (i=0,i<=celkem ,i++){
   srand((unsigned)time(0)); // aby cisla byla na pohled nahodna
   int rozhodovac = rand();
   if (((rozhodovac%2)=0 && celkem_cisel>=0) || celkem_pismen=0){
      // generovani 1 cisla se zapisem do souboru atd., nechce se mi nad tim premyslet
      --celkem_cisel;
   }
   if (((rozhodovac%2)!=0 && celkem_pismen>=0 || celkem_cisel=0){
      // generovani 1 pismena se zapisem do souboru atd
      --celkem_pismen;
   }
}

[spang]

Jenže takhle se ti budou čísla objevovat s mnohem větší pravděpodobností na začátku, než na konci, protože je jich méně.

Já bych potřebný počet čísel i písmen vygeneroval předem a do pořadí z nich vybíral podle daného poměru, výskyt bude rovnoměrný.

[stativ]

Tak příslušně opravit tu dělitelnost proměnné rozhodovac, nebo tuhle část mírně opravit tak, aby tam bylo něco, u čeho je pravděpodobnost pravdivého výsledku odpovídající počtu čísel k nalezení. Pokud by se tam dala delitelnost 3, hned by byla menší pravděpodobnost, že se všechna čísla vypancají na začátku.

[UFI]

Uchovávej si informaci o tom kolik čísel si vygeneroval a tomu přizpůsob pravděpodobnosti při generování dalšího znaku. Pokud už tedy budeš mít plný počet čísel, bude nulová pravděpodobnost vygenerování čísla.

[Radek Trnka]

bohužel hrátky s pravděpodobností nepovolil

[UFI]

To znamená že musí být pořád stejná pravděpodobnost že vygeneruješ číslo? Potom to snad ani nejde udělat.

Leda vygenerovat nejdřív 30 čísel pak 70 znaků a pak ten soubor náhodně zpřeházet :)

[Petr Tomášek]

A co vygenerovat urcity pocet znaku a vedle toho urcity pocet cisel a nejak nahodne zamichat?

[Michal Vyskočil]

Nijak bych se s tím nedrbal a pro rozhodování, co vygenerovat, bych použil pravděpodobnost - vygeneruješ si náhodné číslo z intervalu 0 až 99 a pokud je výsledek z první třetiny, vygeneruješ číslo, jinak znak ...

import random
import re

# vrati znak 0-9
def getNumber():
    return chr(random.randrange(ord('0'), ord('9')))

# vrati A-Za-z
def getChar():
    ret = chr(91)
    while not re.match('[A-Za-z]', ret):
        ret = chr(random.randrange(ord('A'), ord('z')))
    return ret

# pomer pouze ciselnych ku neciselnym
num_ratio = 0.3

# celkovy pocet cisel
count = random.randrange(150, 250)

# generovani
while count:
    if (random.randint(0, 99) <= 100*num_ratio):
        print getNumber()
    else:
        print getChar()    
    count -= 1

Dokonalejší verze by si ještě pamatovala počty už vygenerovaných čísel/znaků, ale s tím se mi popravdě už psát nechtělo

[Honza "tux" Friesse]

Doufám že jsem to z toho popisu pochopil správně.

Implementace v DrScheme

(define (gen-items noitems fromc toc)
  (if (= noitems 0) '() 
        (append (gen-items (- noitems 1) fromc toc) 
                (list (integer->char 
                       (+ (random (+ (- (char->integer toc) (char->integer fromc)) 1)) (char->integer fromc)))))))

(define (shake noshakes str)
  (if (= noshakes 0) str
    (let* ((pos1 (random (string-length str))) (pos2 (random (string-length str))) 
          (ch1 (string-ref str pos1)) (ch2 (string-ref str pos2)))
      (string-set! str pos1 ch2)
      (string-set! str pos2 ch1)
      (shake (- noshakes 1) str))))

      
;Tohle si definuje uzivatel
(define nonums 0.2)
(define nosc   0.3)
(define nolc   0.5)
;A tohle uz se pocita
(define noitems (+ 150 (random (+ 1 (- 250 150)))))

(define str (list->string (append (gen-items (inexact->exact (round (* noitems nolc))) #\A #\Z) 
        (gen-items (inexact->exact (round (* noitems nosc))) #\a #\z) 
        (gen-items (inexact->exact (round (* noitems nonums))) #\0 #\9))))

(shake (* (string-length str) 2) str)

[Kyosuke]

Na můj vkus moc složité a neřeší malá a velká písmena. Já bych na to hrubou silou:

(use srfi-13)
(use srfi-27)

;; Ze znaku retezce retezec generuje nahodny retezec delky delka ;)
(define (nahodny-retezec retezec delka)
  (string-tabulate (lambda _
		     (string-ref retezec (random-integer (string-length retezec))))
		   delka))

;; nahodne prohazi seznam
(define (prohazej seznam)
  (map cdr
       (sort (map (cut cons (random-real) <>) seznam)
	     (lambda (a b) (< (car a) (car b))))))

(define (generuj delka)
  (let* ((cislic (round (* 0.3 delka)))
	 (retezec-k-prohazeni (string-concatenate 
			       (map nahodny-retezec
				    '("abcdefghijklmnopqrstuvxwyzABCDEFGHIJKLMNOPQRSTUVXWYZ"
				      "0123456789")                     ; mnoziny znaku
				    (list (- delka cislic) cislic)))))  ; prislusne pocty
    (list->string (prohazej (string->list retezec-k-prohazeni)))))

(dotimes (i 10) (display (generuj 20)) (newline))

[Kyosuke]

Mimochodem, 1337 řešení pro rub1s7y:

CHARS = (('a'..'z').to_a + ('A'..'Z').to_a)
NUMS = (0..9).to_a

def generate(l)
  c = (l*0.3).round
  t = [[CHARS, l-c], [NUMS, c]].map{|ch, n| Array.new(n){ch[rand(ch.size)]}}
  t.flatten.sort_by {rand}.join
end

Přijde mi rozumně kompaktní a dá se rozšířit na více skupin ekvivalence

[skeptik]

Chceš-li mít zastoupení "přesné" (až na zaokrouhlení) a přesto opravdu náhodné pořadí, nezbývá ti než vygenerovat písmena a čísla zvlášť (znak po znaku to z principu nejde) a pak je teprve náhodně seřadit (např. přes pomocný přiřazený double). Je to časově náročnější, ale jedině tak to bude "přesné".

[Radek Trnka]

Takže díky za rady. Nyní jsem dospěl do stádia kdy mám přesné procenta, ale vždy mi ulítne 1 až 2 znaky navíc. Vypadá to nějak takto :

if ((procent>0) and (procent<100)) then {generuje pismena i znaky}
    begin
      cisel:=Int((pocet/100)*procent);
      pismen:=(pocet-cisel);
      c:=0;
      p:=0;

    for i:=1 to ((pocet)) do
     begin
      pom:=random(2);

      if ((pom=0) and (c<>cisel)) then
           generuj_cisla;

      if ((pom=0) and (c=cisel)) then
           generuj_znaky;

      if ((pom=1) and (p<>pismen)) then
           generuj_znaky;

      if ((pom=1) and (p=pismen)) then
           generuj_cisla;
     end
  end;

Generuj_cisla a generuj_znaky jsou procedury, které vypadají takto :

procedure generuj_cisla;
begin
   znak := random(10)+48; {generuje cisla}
   c:=c+1;
   write(vystup,chr(znak));
end;

procedure generuj_znaky;
begin
 if (random(2))=0 then
   begin
     znak := random(26)+65; {generuje velka pismena}
     p:=p+1;
     write(vystup,chr(znak))
   end
 else
   begin
     znak := random(26)+97; {generuje male pismena}
     p:=p+1;
     write(vystup,chr(znak));
   end;
end;

Netušíte někdo jak to odladit aby mi neulítával ten jeden či dva znaky? Vyjma možnosti, že je na konci spočítám a přebývající smažu.

[zuzi]

Za predpokladu ze by to misto nul generovalo znaky a misto jednicek cisla tak je to to cos hledal?

int main(int argc,char **argv)
{
   // pocet znaku
   const int count = 1000;

   // pomer
   float rate = 0.256;
   int zero_rate = (int)(rate*(float)count);
   int sum = count;

   int z_cnt = 0;
   int o_cnt = 0;

   do {
      if (rand()%sum < zero_rate) {
         putchar('0');
         z_cnt++;
         zero_rate--;
      }
      else {
         putchar('1');
         o_cnt++;
      }
   } while(--sum > 0);

   register float f_count = (float)count;
   printf("\nfinal rate: %f : %f\n",(float)z_cnt/f_count,(float)o_cnt/f_count);

   return 0;
}

[Lukáš Zapletal]

cat /dev/urandom | tr -cd A-Za-z0-9 | fold -w8 | head -n 1

[Kyosuke]

A co procentní podíly? Ale cat+tr je dobrá kombinace.