Přihlásit
: [1]
   |   
: permutace, variace, kombinace v bashi  ( 4624 )
Ged
Full Member
***

Karma: 3
: 215


17002977
« : December 06, 2010, 18:36:09 »

Nekdy potrebuji z mnoziny n prvku generovat variace, ....

Neexistuji v bashi uz nejake vestavene funkce, ktere by mi to ulehcily?

Pripadne nemate/neznate nejak skripty, ktere to umi.

Nechce se mi objevovat ameriku. V google jsem nic rozumneho nenasel.

Pocet generovanych objektu by byl max radove ve 100-kach takze by mi nevadilo i nejake neoptimalizovane reseni primo v bashi.

Dekuji.

Jednou jsem ho videl na vanoce

Gold "3-Ethyl-1,2,2-trimethyl-bicyclo[2.1.0]pentane"

jabber: uranit@jabbim.cz
_dworkin


« #1 : December 16, 2010, 16:10:26 »

:
#!/bin/bash

# variace s opakovanim
prvku=3
delka=4

prvky=("0" "1" "X")

# pole pomocne udrzuje pouzite indexy do pole prvku na danych pozicich
for (( a=0 ; $a-delka ; a=$a+1 )) ; do pomocne[$a]=0; done

zmena=0
while [ 1 ]; do
   for (( a=0 ; $a-delka ; a=$a+1 )) ; do vypis[$a]=${prvky[${pomocne[$a]}]};  done
   echo ${vypis[*]}
   
   pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   while [ ${pomocne[$zmena]} == $prvku ]; do
         pomocne[$zmena]=0
         zmena=`expr $zmena + 1`
         [ $zmena == $delka ] && exit;
         pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   done
   zmena=0
   
done

:
bash-4.1$ ./variace.sh
0 0 0 0
1 0 0 0
X 0 0 0
0 1 0 0
1 1 0 0
X 1 0 0
0 X 0 0
1 X 0 0
X X 0 0
0 0 1 0
1 0 1 0
X 0 1 0
0 1 1 0
1 1 1 0
X 1 1 0
0 X 1 0
1 X 1 0
X X 1 0
0 0 X 0
1 0 X 0
X 0 X 0
0 1 X 0
1 1 X 0
X 1 X 0
0 X X 0
1 X X 0
X X X 0
0 0 0 1
1 0 0 1
X 0 0 1
0 1 0 1
1 1 0 1
X 1 0 1
0 X 0 1
1 X 0 1
X X 0 1
0 0 1 1
1 0 1 1
X 0 1 1
0 1 1 1
1 1 1 1
X 1 1 1
0 X 1 1
1 X 1 1
X X 1 1
0 0 X 1
1 0 X 1
X 0 X 1
0 1 X 1
1 1 X 1
X 1 X 1
0 X X 1
1 X X 1
X X X 1
0 0 0 X
1 0 0 X
X 0 0 X
0 1 0 X
1 1 0 X
X 1 0 X
0 X 0 X
1 X 0 X
X X 0 X
0 0 1 X
1 0 1 X
X 0 1 X
0 1 1 X
1 1 1 X
X 1 1 X
0 X 1 X
1 X 1 X
X X 1 X
0 0 X X
1 0 X X
X 0 X X
0 1 X X
1 1 X X
X 1 X X
0 X X X
1 X X X
X X X X
_dworkin


« #2 : December 16, 2010, 16:15:14 »

oprava:
:
#!/bin/bash

# variace s opakovanim
prvku=3
delka=4

prvky=("0" "1" "X")

# pole pomocne udrzuje pouzite indexy do pole prvku na danych pozicich
for (( a=0 ; $a-delka ; a=$a+1 )) ; do pomocne[$a]=0; done


while [ 1 ]; do
   for (( a=0 ; $a-delka ; a=$a+1 )) ; do vypis[$a]=${prvky[${pomocne[$a]}]};  done
   echo ${vypis[*]}

   zmena=0  
   pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   while [ ${pomocne[$zmena]} == $prvku ]; do
         pomocne[$zmena]=0
         zmena=`expr $zmena + 1`
         [ $zmena == $delka ] && exit;
         pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   done
  
done
_dworkin


« #3 : December 16, 2010, 16:46:29 »

Variace bez opakovani

:
#!/bin/bash

# variace bez opakovani
prvku=3
delka=3

prvky=("0" "1" "X")

# pole pomocne udrzuje pouzite indexy do pole prvku na danych pozicich
for (( a=0 ; $a-delka ; a=$a+1 )) ; do pomocne[$a]=0; done


while [ 1 ]; do
   # test jestli se indexy opakuji
   opakovani=0
   for (( a=0 ; $a-delka ; a=$a+1 )) ; do
      for (( b=$a+1 ; $b-delka ; b=$b+1 )) ; do
          if [ ${pomocne[$a]} == ${pomocne[$b]} ]; then opakovani=1; fi
      done
   done

   if [ $opakovani == 0 ]; then
      for (( a=0 ; $a-delka ; a=$a+1 )) ; do vypis[$a]=${prvky[${pomocne[$a]}]};  done
      echo ${vypis[*]}
   fi

   zmena=0   
   pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   while [ ${pomocne[$zmena]} == $prvku ]; do
         pomocne[$zmena]=0
         zmena=`expr $zmena + 1`
         [ $zmena == $delka ] && exit;
         pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   done
   
done
:
bash-4.1$ ./variace2.sh
X 1 0
1 X 0
X 0 1
0 X 1
1 0 X
0 1 X
_dworkin


« #4 : December 16, 2010, 17:10:31 »

Kombinace:
:
#!/bin/bash

# kombinace
prvku=4
delka=3

prvky=("0" "1" "X" "Y")

# pole pomocne udrzuje pouzite indexy do pole prvku na danych pozicich
for (( a=0 ; $a-delka ; a=$a+1 )) ; do pomocne[$a]=0; done


while [ 1 ]; do
   # test jestli jsou indexy vetsi nez predchozi
   opakovani=0
   for (( a=0 ; $a-delka ; a=$a+1 )) ; do
      for (( b=$a+1 ; $b-delka ; b=$b+1 )) ; do
          if [ ${pomocne[$a]} -le ${pomocne[$b]} ]; then opakovani=1; fi
      done
   done

   if [ $opakovani == 0 ]; then
      for (( a=0 ; $a-delka ; a=$a+1 )) ; do vypis[$a]=${prvky[${pomocne[$a]}]};  done
      echo ${vypis[*]}
   fi

   zmena=0   
   pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   while [ ${pomocne[$zmena]} == $prvku ]; do
         pomocne[$zmena]=0
         zmena=`expr $zmena + 1`
         [ $zmena == $delka ] && exit;
         pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   done
   
done
:
bash-4.1$ ./kombinace.sh
X 1 0
Y 1 0
Y X 0
Y X 1
_dworkin


« #5 : December 16, 2010, 18:41:02 »

Kombinace zrychleni
:
#!/bin/bash

# kombinace
prvku=5
delka=4

[ $prvku -lt $delka ] && exit

prvky=("0" "1" "X" "Y" "Z")

# pole pomocne udrzuje pouzite indexy do pole prvku na danych pozicich
for (( a=0 ; $a-delka ; a=$a+1 )) ; do pomocne[$a]=$a; done

while [ 1 ]; do
 
   for (( a=0 ; $a-delka ; a=$a+1 )) ; do vypis[$a]=${prvky[${pomocne[$a]}]};  done
   echo ${vypis[*]}
 
   zmena=0
   pak=1
   if [ $delka -le 1 ]; then dalsi=$prvku ; else dalsi=${pomocne[1]}; fi
   pomocne[0]=`expr ${pomocne[0]} + 1`

   while [[ ${pomocne[$zmena]} == $prvku || ${pomocne[$zmena]} -ge $dalsi ]]; do
         pomocne[$zmena]=$zmena
         zmena=$pak
         [ $zmena == $delka ] && exit;
         pak=`expr $pak + 1`
         if [ $pak -ge $delka ]; then dalsi=$prvku ; else dalsi=${pomocne[$pak]}; fi
         pomocne[$zmena]=`expr ${pomocne[$zmena]} + 1`
   done
   
done
Ged
Full Member
***

Karma: 3
: 215


17002977
« #6 : December 17, 2010, 07:28:17 »

Dekuji. Hned vyzkousim.

Na jinem foru jsem se dozvedel, ze bych mohl pouzit vystup z pythonu http://docs.python.org/library/itertools.html nebo bc, ale pripadlo mi to pro me ucely jako "kanon na vrabce".


Jednou jsem ho videl na vanoce

Gold "3-Ethyl-1,2,2-trimethyl-bicyclo[2.1.0]pentane"

jabber: uranit@jabbim.cz
: [1]
   |   
 
: