Mandriva Fórum

Programování => Shell, awk, sed ... => : Ged December 06, 2010, 18:36:09



: permutace, variace, kombinace v bashi
: Ged 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.


: Re: permutace, variace, kombinace v bashi
: _dworkin 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


: Re: permutace, variace, kombinace v bashi
: _dworkin 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


: Re: permutace, variace, kombinace v bashi
: _dworkin 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


: Re: permutace, variace, kombinace v bashi
: _dworkin 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


: Re: permutace, variace, kombinace v bashi
: _dworkin 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


: Re: permutace, variace, kombinace v bashi
: Ged 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 (http://docs.python.org/library/itertools.html) nebo bc, ale pripadlo mi to pro me ucely jako "kanon na vrabce".