Re: [shell-script] lista de palavras shuf combinação

[MrBiTS]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

| ???Como faço para extrair todas as combinações possíveis de uma lista de
| palavras???
|
| Resolvi o problema de como extrair *uma* combinação possível mas não consigo
| resolver para "todas" e por isso recorro à lista.
|
| **Explicação do problema**
|
| Tenho uma lista de palavras da forma:
|
| palavra0
| palavra1
| palavra2
| palavra3
| palavra4
| palavra5
| palavra6
| palavra7
| palavra8
| palavra9
| ...
| ...
| ...
| palavraN
|
|
| onde N é variável que estão gravadas no arquivo x.txt sendo uma palavra por
| linha.
|
| Preciso extrair todas as combinações possíveis de palavras. Se o arquivo tiver
| 10 linhas/palavras o script deve solicitar a quantidade de linhas que desejo
| na saída (digamos y) e gravar todas as saídas possíveis com aquele número de
| linhas em vários arquivos sendo cada arquivo com as linhas solicitadas (y no
| caso).
|
| se o arquivo de entrada tiver 10 linhas e eu solicitar 5 linhas na saída o
| script me deve retorar 252 arquivos cada um com 5 palavras e todos os
| arquivos diferentes um do outro.
|
| se o arquivo de entrada tiver 5 linhas e eu solicitar 3 linhas na saída o
| script me deve retorar 10 arquivos cada um com 3 palavras e todos os arquivos
| diferentes um do outro.
|
|
| ***solução parcial***
| A solução para extrai uma combinação é a seguinte:
|
| ARQUIVO="x.txt"
| PALAVRAS=`wc -l $ARQUIVO | cut -d ' ' -f 1`
| ARQUIVO1=`mktemp`
| echo $PALAVRAS
| echo "Quantas palavras você deseja extrair?" ; read N
| echo $N
| if [ $N -ge $PALAVRAS ]
|  then
|     echo "é maior ou igual"
|     exit
| fi
| shuf $ARQUIVO > $ARQUIVO1
| tail -$N $ARQUIVO1 > y.txt

Isso tem uma cara de ser trabalho escolar e a dúvida é mais de lógica de 
programação que de shell-script propriamente dito. Seu
script faz pouco mais que nada.

Em nenhum momento você faz um laço para gerar suas combinações e o shuf não 
resolve seu problema, visto que gera uma combinação
aleatória. Você poderia jogar o shuf num laço, mas corre o risco de gerar 
combinações iguais.

Para isso você precisa aplicar conceitos de análise combinatória. Você nos diz 
que quer combinações ( não arranjos, nem permutas ).
E, mais, você quer fazer uma combinação de N elementos ( quantidade de palavras 
do arquivo ) agrupadas em K blocos. Então, primeiro,
como não sabemos a quantidade de linhas que temos no arquivo, vamos fazer um 
simples wc -l nele para conseguir essa informação e
aplicar a fórmula de combinação:

Cn,k = n! / k!(n-k)!

Eu mesmo tenho um scriptzinho que me dá a quantidade de combinações que 
determinados N, K, me darão. Adaptei-a um pouco para o seu
problema, lendo o seu arquivo e gerando a quantidade de linhas que ele tem:

<code>

#!/bin/bash
fatorial ()  {
~        local NUMBER=$1
~        if [ "${NUMBER}" -gt "1" ]; then
~            I=$(expr ${NUMBER} - 1)
~            J=$(fatorial ${I})
~            RET=$(expr ${NUMBER} \* ${J})
~            echo ${RET}
~        else
~            echo 1
~        fi
}

ARQUIVO="d.txt"

# Gerando N, K
N=$(awk 'END{print NR}' ${ARQUIVO})
read -p "Quantas palavras deseja extrair ? " K

FN=$(fatorial ${N})
FK=$(fatorial ${K})
FNmK=$(fatorial $((${N} - ${K})))

# Calculando combinacoes a partir da formula:
# Cn,k = n! / k!(n-k)!

CNK=$(expr ${FN} \/ ${FK} \* ${FNmK})

echo "Serao geradas ${CNK} combinacoes"

</code>   

Isso você já fez, visto que tem os números de combinações geradas no seu 
exemplo de N = 5 e K = 3. Falta aplicar um for nesses casos
para gerar a listagem.

Então, falta um laço para você ler as palavras do arquivo, jogá-las numa matriz 
e lê-las progressivamente. Achei bastante coisa no
Google sobre algorítmos de combinações, visto que é um problema matemático 
clássico.


- --

Um abraço

.0. MrBiTs - address@hidden
..0 GnuPG  - 
http://keys.cardboard.net:11371/pks/lookup?op=get&search=0xAC37715A6DD1F186
000 http://www.mrbits.com.br

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFIg5nJrDdxWm3R8YYRAoSqAJ4lPdOQpUORwxL+Zo3ATMYB1Ewm6ACfZ6Kd
O1LSPNTCg3jEv4QUHLRBJoQ=
=Ah6W
-----END PGP SIGNATURE-----