How to make permutation in bash with N! input?

Question

I have to make a permutation in bash with "eval" and "seq" commands. So I have to make first a permutation that could contain the same numbers, then I have to filter it somehow.

The teacher told me I have to use two cycle/period, one in the other. But I don't know how to do it.

The input is like:

The output should be:

If someone could help me, that would be great!

Edit: I want to know how to do it with these commands, my friend made it to me like this: http://pastebin.com/wM2U1SuT the teacher told me its too good, were not on this level.. i should do it with seq and eval, even if its not that good then. The second problem was that the input was 123, not 3, like 3!..

What specifically do you want to know? What code have you written so far? [ask] — Håken Lid, Jun 05 '16 at 08:57
Your teacher's priorities are seriously suspect if they are teaching `eval` before anything in the posted example. — chepner, Jun 05 '16 at 14:11
You're right, but Im here on the site, where people can make questions, and usually other people answer those questions. I don't think that I did something wrong.. Yeah I know, that I'm not as good as you guys here.. That's why Im here. — hategrip, Jun 05 '16 at 19:43
I didnt even think that i cant get a solution for this problem. I thought its easy just im bad. :D I had one lesson a week, overall 15hours of Linux, about 5hours of scripting and using bash.. I really need someone who understands this thing.. — hategrip, Jun 05 '16 at 19:48
The problem is it's like if you were asking a group of painters how to paint a wall using just a magnetic screwdriver and a pint of frozen yogurt. None of the painters would know off the top of their head how to do that because it's not something they'd ever do so they'd have to put time and effort into figuring out some way to do this odd thing you're asking for and so there's just not that many painters around who'd feel compelled to do so given it's not something anyone should ever really do. I do sympathize though - good luck! — Ed Morton, Jun 05 '16 at 21:29
hahaha very nice comparison :) I know you're right.. thank you for the answers! — hategrip, Jun 06 '16 at 07:50

score 1 · Answer 1 · edited May 23 '17 at 11:52

1

It is a permutation problem, so I have found some others have did it. You can see the answer Generating permutations using bash

So through the answer, you can write the code like this:

perm() {
    local items="$1"
    local out="$2"
    local i
    [[ "$items" == "" ]] && echo "$out" && return
    for (( i=0; i<${#items}; i++ )) ; do
        perm "${items:0:i}${items:i+1}" "$out${items:i:1}"
    done
}

test() {
    local number="$1"
    local iniitem="$(seq -s' ' 1 ${number} | sed -n 's/ //g;p')"
    perm "$iniitem"
}

Then you can use the function like this:
test 3:
the output:

edited May 23 '17 at 11:52

Community

1
1

answered Jun 05 '16 at 09:42

zhenguoli

2,268
1
14
31

thanks for the answer, but i have to use those commands. :( but very kind of you guys appreciate it! – hategrip Jun 05 '16 at 11:26
only use `eval` and `seq`, no other commands are possible? If you want to input is `123`, you can just use the `perm 123`. – zhenguoli Jun 05 '16 at 11:30
eval and seq yes.. and two cycle/period, one in the other. he told me do first a "recurring" permutation, the filter it.. and the input must be one number like: 4, then the output is 1234, 1243, 1342, 1324..etc. – hategrip Jun 05 '16 at 11:54
I don't know why can't you use other commands, if you use `eval`, you can change the program to strings and then `eval 'the string'`, but the string also contain other commands, too, like `eval 'echo hello'`, the `echo` string is also executed as a command, maybe the effect is the same. – zhenguoli Jun 05 '16 at 11:58
Why you edit the problem that the input is `123`, not `3`, but you say the input is `4` again, are they conflict? – zhenguoli Jun 05 '16 at 12:02
I think it doesnt matter, if the input is 3, or 4. The important is that, that the input must be one number, and the program will handle the input (like3) as 123. Sorry my english is not perfect, I cant even describe my problem. He told me to do a "recurring" permutation, where the number can be the same like 133, 221, then in two periods I have to take them out somehow.. im soo nooob sorry guys :( – hategrip Jun 05 '16 at 12:13
The program above is a `recurring` permutation, the `perm` invokes itself in the `perm "${items:0:i}${items:i+1}" "$out${items:i:1}"`. Sorry, maybe I still haven't understand the problem. I also can't access the site [http://pastebin.com/wM2U1SuT](http://pastebin.com/wM2U1SuT) to see the code, sorry. And my english is also pool. – zhenguoli Jun 05 '16 at 12:19
that was the link, but its just a picture: https://gyazo.com/71c5b339509978cb960304e0f754384d the problem is that i have to do it like he wants to, even if these are correct answers for my question. He want to see these commands and a two if commands, one in the other. – hategrip Jun 05 '16 at 12:24
The program is the same as the program above, maybe a little different. You mean use `seq` and `eval` and a two `if` construct? – zhenguoli Jun 05 '16 at 12:28
yeah, i mean that was a good program but the teacher said were not on this level yet.. and yepp, like you said, seq, and eval and a two if contruct. – hategrip Jun 05 '16 at 12:50
What the meaning of `not on this level yet`? I can't implement the requirement you have been required, sorry. – zhenguoli Jun 05 '16 at 12:53
Too good, ^_^? And you should check your `typo`, it will be misunderstanding. – zhenguoli Jun 05 '16 at 13:19
can someone help me? :( – hategrip Jun 05 '16 at 19:15
That's hard to answer since you're asking for help to create a solution that must do 2 things you should never do so there's no good solution. Read [why-is-using-a-shell-loop-to-process-text-considered-bad-practice](http://unix.stackexchange.com/questions/169716/why-is-using-a-shell-loop-to-process-text-considered-bad-practice) and [why-should-eval-be-avoided-in-bash-and-what-should-i-use-instead](http://stackoverflow.com/questions/17529220/why-should-eval-be-avoided-in-bash-and-what-should-i-use-instead) – Ed Morton Jun 05 '16 at 19:42
I found the soution:) – hategrip Jun 07 '16 at 17:17
Congratulations! Can you answer your question to share your code? You have done it. Thanks! – zhenguoli Jun 08 '16 at 04:44

Ed Morton · Answer 2 · 2016-06-05T21:19:40.943

I understand this isn't the seq+eval solution the OP wants but in case anyone in future is looking for an alternative, here's an implementation of the generate() function described in the Wikipedia article on Heap's Algorithm written in awk to solve this problem:

$ cat tst.awk
function generate(n,A,  i) {
    if (n == 1) {
        output(A)
    }
    else {
        for (i=0; i<(n-1); i++) {
            generate(n-1, A)
            swap(A, (n%2?0:i), n-1)
        }
        generate(n-1, A)
    }
}

BEGIN{
    if (n>0) {
        for (i=1; i<=n; i++) {
            A[i-1] = i
        }
        generate(n, A)
    }
}

function output(a, i,g) {g=length(a); for (i=0;i<g;i++) printf "%s%s",a[i],(i<(g-1)?"":ORS)}
function swap(a,x,y, t) {t=a[x]; a[x]=a[y]; a[y]=t }

$ awk -v n=3 -f tst.awk | sort
123
132
213
231
312
321

I stuck to the Wikipedia article naming and other conventions as much as possible, including starting the array at zero instead of the typical awk 1, for ease of comparison between that article and the awk code.

score 1 · Accepted Answer · edited Jun 08 '16 at 06:21

If someones curious, heres the solution:

input=3
for i in $(eval echo " {1..$input}{1..$input}{1..$input} "); do
    OK=yes
    for pos1 in $(seq 0 $((x,1)) ); do
        for pos2 in $(seq 0 $((x,1)) ); do
            if [ $pos1 != $pos2 ]; then
                if [ ${i:$pos1:1} == ${i:$pos2:1} ]; then
                    OK=no
                fi
            fi
        done
    done
    if [ $OK = yes ]; then
        echo $i
    fi

done

How to make permutation in bash with N! input?

3 Answers3

Linked