permutation combination by position number in bash?

[blumenwesen]

I found this script and would like to find a specific combination by its number in the sequence.
If 4312 comes in position 23, can this combination be found just by calculating the sequence number 23 without comparing and running through all possible sequences?
Otherwise it takes too long with bash and I don't know other languages ​​well enough to modify the code. Moreover, bash is more stable than python or java when it comes to updates and changes to the code structure.
I was looking for a calculation method but unfortunately I'm a math idiot and Spanish is probably easier to understand than knowing which is the correct calculation method and then applying it to an array which only shows the desired combination sequence by specifying the position in the sequence.

Code: Select all

n=23; i=0; while read in; do 
nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)
[[ $nr == 5 ]] && i=$[$i+1]
[[ $nr == 5 && $n == $i ]] && out=$in && break
done <<<$(echo -e {1..4}{1..4}{1..4}{1..4}"\n")
echo $out #4312

[Chelsea80]

@blumenwesen

First things first.

I have used this AI Answer Anything before. And yes it has given wrong information, so it's up to you to try and unpick and verify.

Anyway, it's all I can offer but my guess is you need someone who understands code to be definitive.

What does this script do?

n=23; i=0; while read in; do
nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)
[[ $nr == 5 ]] && i=$[$i+1]
[[ $nr == 5 && $n == $i ]] && out=$in && break
done <<<$(echo -e {1..4}{1..4}{1..4}{1..4}"\n")
echo $out #4312

Answer

This script is a Bash script that performs a specific task involving generating combinations of numbers, counting unique digits, and finding a particular combination based on certain conditions. Let's break down what each part of the script does:

Script Breakdown

Initialization:

bash
n=23
i=0

n is initialized to 23. This is the target count of combinations that meet a certain condition.
i is initialized to 0. This will be used to count how many combinations have met the condition so far.

While Loop:

bash
while read in; do

The while loop reads each line of input from a here-string provided by the <<< operator at the end of the script.

Generating Combinations:

bash
done <<<$(echo -e {1..4}{1..4}{1..4}{1..4}"\n")

echo -e {1..4}{1..4}{1..4}{1..4}"\n" generates all possible combinations of four digits where each digit can be 1, 2, 3, or 4. This results in 4^4 = 256 combinations.

The combinations are fed into the while loop one by one.

Counting Unique Characters:

bash
nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)

sed -r "s/(.)/\1\n/g" <<<$in takes the input string $in and inserts a newline after each character, effectively splitting the string into individual characters.
sort | uniq sorts the characters and removes duplicates.
wc -l counts the number of unique characters.

Checking Conditions:

bash
[[ $nr == 5 ]] && i=$[$i+1]
[[ $nr == 5 && $n == $i ]] && out=$in && break

The first condition checks if the number of unique characters ($nr) is 5. If true, it increments the counter i.
The second condition checks if the number of unique characters is 5 and if i equals n (23). If both conditions are met, it assigns the current combination to out and breaks the loop.

Output:

bash
echo $out #4312

Finally, it prints the value of out, which is the 23rd combination that has exactly 5 unique characters. However, since the maximum possible number of unique characters in a four-digit string composed of digits 1-4 is 4, this condition can never be met. Therefore, the script will never reach the echo $out line with a valid output, and the comment #4312 seems incorrect or misleading in this context.

Conclusion
The script seems to have a logical flaw because it is impossible for a four-digit combination of numbers from 1 to 4 to have 5 unique characters. Therefore, the condition [[ $nr == 5 ]] will never be true, and the script will not produce a valid output. The comment #4312 seems to be incorrect or based on a misunderstanding of the script's logic.

Hope this helps

[blumenwesen]

the simpler would be "1 2 3" and the fifth combination position is "312" out of six possible variants.
how can the combination "312" be calculated only by specifying the number of all elements "3", the maximum possible variants "6" and individual variants position "5"?
It is actually more math than bash, but since there is only one sequence of an order, it is completely logical and predictable, so there must be a calculation path, but unfortunately I don't know one.

Code: Select all

while read in; do 
nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)
[[ $nr == 4 ]] && echo $in
done <<<$(echo -e {1..3}{1..3}{1..3}"\n")

perhaps the factor calculation can be adjusted.

Code: Select all

z=1; y=3; 
x=$z; until (( $y <= 0 )); do 
x=$[$x*$y]; 
y=$[$y-1]; 
done; 
echo $x

[some1]

Conclusion
The script seems to have a logical flaw because it is impossible for a four-digit combination of numbers from 1 to 4 to have 5 unique characters. Therefore, the condition [[ $nr == 5 ]] will never be true, and the script will not produce a valid output. The comment #4312 seems to be incorrect or based on a misunderstanding of the script's logic.

Hope this helps

The AI just does not get it - talking-head-under-arm.
The sed inserts a trailing newline -
which is included in the wc -l count -
so the limit IS nr == 5
------
The code seem to work -
BUT it is MUCH too slow -
imagine looping 4**4 times around
4 binary-calls:
Get rid of this time-waster:

nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)

A bash-array can do the sorting,uniqueness and count
per 4-digit-item.

[some1]

Code: Select all

#!/bin/bash

time {
n=23; i=0; while read in; do
 
nr=$(sed -r "s/(.)/\1\n/g" <<<$in | sort | uniq | wc -l)

[[ $nr == 5 ]] && i=$[$i+1]
[[ $nr == 5 && $n == $i ]] && out=$in && break
done <<<$(echo -e {1..4}{1..4}{1..4}{1..4}"\n")
echo $i:$out 
}
#23:4312

#real	0m0.923s
#user	0m1.920s
#sys	0m1.107s

exit
time {

k=23
n=$k; i=0;
for x in {1..4}{1..4}{1..4}{1..4}" ";do
ar=()
ar+=([ ${x:0:1} ]=1 [ ${x:1:1} ]=1 [ ${x:2:1} ]=1 [ ${x:3:1} ]=1)    

nr=${#ar[@]}


#[[ $nr == 4 ]] && i=$[$i+1]
(((nr == 4) && i++))
#[[ $nr == 4 && $n == $i ]] && out=$x && break
(((nr == 4) && (n == i))) && out=$x && break
done
echo "$k:$out" 

}

#23:4312 

#real	0m0.006s
#user	0m0.005s
#sys	0m0.001s

exit

[blumenwesen]

Thanks for the help runs much faster, i dynamically adjusted it so that only the base "{1..4}{1..4}{1..4}{1..4}" must be changed.
Came across interesting data that the mathematical basis 9 or 3 reveals, no matter what length the number arrangement has.
I am not further and it is certainly very difficult to find a system when the numbers vary so much, but I will never give up climbing the pyramid of knowledge.

=)

Code: Select all

ar0=(); z=0; 
until ! read y; do 
eval "x=\$(echo -e \\\x5B\\\x24\\\x7By\\\x3A{0..$[${#y}-1]}\\\x3A1\\\x7D\\\x5D\\\x3D1); ar1=(); ar1+=($x)"; 
[[ ${#ar1[@]} == ${#y} ]] && ar0[$z]=$y && z=$[$z+1] && echo "$y-${ar0[$z-2]}="$[ $y-${ar0[$z-2]} ]; 
done <<<$(echo -e {1..4}{1..4}{1..4}{1..4}"\n")

123-321=-198
132-123=9 3*3=9
213−132=81 9*9=81
231-213=18 3*6=18
312-231=81 9*9=81
321-312=9 3*3=9

1234-4321=-3087
1243-1234=9
1324-1243=81
1342-1324=18
1423-1342=81
1432-1423=9
2134-1432=702
2143-2134=9
2314-2143=171
2341-2314=27
2413-2341=72
2431-2413=18
3124-2431=693
3142-3124=18
3214-3142=72
3241-3214=27
3412-3241=171
3421-3412=9
4123-3421=702
4132-4123=9
4213-4132=81
4231-4213=18
4312-4231=81
4321-4312=9

693/9=77
3087/9=343

[blumenwesen]

I found this code, but it also seems to be a run of all variants and then a comparison with the searched, I'm not quite sure.

https://www.geeksforgeeks.org/find-the- ... l-numbers/

Have now searched a lot but unfortunately not found a calculation option, although the order has already been determined beforehand.
Whether a superficially effective solution was found for this problem only through the invention of the computer.
=D
The Internet contains a number of struggles and the same principle, but if someone is looking for different information, you need one of the high mathematicians.

[Burunduk]

I found this script and would like to find a specific combination by its number in the sequence.
If 4312 comes in position 23, can this combination be found just by calculating the sequence number 23 without comparing and running through all possible sequences?

Bash has a very limited support for math. In python, you don't even need to code to solve this particular problem - it has a function for this already:
more_itertools.nth_permutation(iterable, r, index)

There is also a code snippet in C on stackoverflow. It's simple and can be used in bc almost verbatim:

Code: Select all

#!/bin/bash

bc << EOM
# The number of entries
n = $1
# The index of the permutation (starts from 1)
i = $2 - 1
j = 0
k = 0

fact[k] = 1
while (++k < n)
  fact[k] = fact[k - 1] * k

for (k = 0; k < n; ++k) {
  perm[k] = i / fact[n - 1 - k]
  i = i % fact[n - 1 - k]
}

for (k = n - 1; k > 0; --k)
  for (j = k - 1; j >= 0; --j)
    if (perm[j] <= perm[k])
      perm[k] += 1

for (k = 0; k < n; ++k)
  print perm[k] + 1, " "
print "\n"
EOM

Running this script with your example:

Code: Select all

root# ./nth_permutation 4 23
4 3 1 2 
root# ./nth_permutation 3 5
3 1 2 
root# 

[blumenwesen]

Runs well and is very fast, so I will soon be able to calculate the course of the individual rooms in the hypercube.
Thanks for the script, I have adapted it in bash.

Code: Select all

n=5
i=$[50-1]
fact=(1)
for (( k=1; k<n; k++ )); do 
  fact[$k]=$(( ${fact[$(( k - 1 ))]} * k ))
done

perm=()
for (( k=0; k<n; k++ )); do 
  perm[$k]=$(( i / ${fact[$(( n - 1 - k ))]} ))
  i=$(( i % ${fact[$(( n - 1 - k ))]} ))
done

for (( k=$(($n - 1)); k>0; k-- )); do 
  for (( j=$(($k - 1)); j>=0; j-- )); do 
    if [[ ${perm[$j]} -le ${perm[$k]} ]]; then
      perm[$k]=$(( ${perm[$k]} + 1 ))
    fi
  done
done

for (( k=0; k<n; k++ )); do 
  printf "%d " $(( ${perm[$k]} + 1 ))
done
echo ""