2

I want to create a large number of folders and do some operations in them. The folder names are based on permutations of several chemical elements which I define as variables in a for loop:

for Element in Cr Hf Mo Nb Ta Ti V W Zr

I want a folder for all permutations of 4 of the elements in alphabetical order, so that I get subfolders containing the letters CrHfMoNb, CrHfMoTa, ... and so on. I tried to do this with 4 nestled for loops, but for simplicity I will demonstrate it here with just 2. The code I have come up with is:

for Element in Cr Hf Mo Nb Ta Ti V W Zr; do
    for Elemen in Hf Mo Nb Ta Ti V W Zr; do
        mkdir "$Element""$Elemen"N     # the N at the end is intended
    done
done

This yields the folders I want but a lot of unnecessary ones too, because I also get combinations like TiNbN or ZrVN which are not alphabetic and also duplicates like HfHfN. I can get rid of the duplicates by adding an if statement to the third line

do [ "$Element" != "$Elemen" ] && mkdir "$Element""$Elemen"N

although these duplicate folders do not disappear completely but become "phantom" files in my directory, meaning that they are called HfHfN etc. but have no file extension. The real problem however is the rest of the folders. I tried adding more if statements like

do [ "$Element" != "$Elemen" ] && [ "$Element" > "$Elemen" ] && mkdir "$Element""$Elemen"N

to decrease the allowed number of permutations but this does not get rid of anything. I also tried separating the if statements into their own respective for loops but that does not change anything aswell:

for Element in Cr Hf Mo Nb Ta Ti V W Zr; do
    [ "$Element" != "$Elemen" ] && [ "$Element" > "$Elemen" ] &&
    for Elemen in Hf Mo Nb Ta Ti V W Zr;  do...

I'm not entirely sure if > is the right if command, but from this list http://tldp.org/LDP/Bash-Beginners-Guide/html/sect_07_01.html it seems the most reasonable one. Using commands like -ne, -lt, -le, -gt does not work as well, because they demand an integer, so the letters are not accepted. In the end I want to combine 4 loops together so it becomes a bit difficult to see through. What am I missing?

1

Spend a couple steps on skipping redundancies. It'll speed up the process overall.

declare -a lst=( Cr Hf Mo Nb Ta Ti V W Zr ) # make an array
for a in ${lst[@]}                          # for each element
do  for b in ${lst[@]:1}                    # for each but the 1st
    do [[ "$b" > "$a" ]] || continue        # keep them alphabetical and skip wasted work
        for c in ${lst[@]:2}                # for each but the first 2
        do  [[ "$c" > "$b" ]] || continue   # keep them alphabetical and skip wasted work
            for d in ${lst[@]:3}            # for each but the first 3
            do [[ "$d" > "$c" ]] || continue # keep them alphabetical and skip wasted work
                mkdir "$a$b$c$d" && echo "Made: $a$b$c$d" || echo "Fail: $a$b$c$d"
            done
        done
    done
done

The redundancy skips are for when later loops are starting, such as when the outer loop is on element 4 but the second loop is still on 3 or 4. These skip those, because they wouldn't be alphabetic combinations. Doing that also guarantees no repeats. This generated 126 distinct dirs with no errors in 0m8.126s in git bash on my laptop with no subshells other than mkdir.

| improve this answer | |
6
#/bin/sh

# shellcheck disable=SC2046
# ^ word-splitting by the shell is intentional in this file

elems="Cr Hf Mo Nb Ta Ti V W Zr"
for a in $elems
do
    for b in $elems
    do
        for c in $elems
        do
            for d in $elems
            do
                # for a set of any four elements:
                #   string them together, separated by NUL-bytes
                #   sort them lexicographically ...
                #     ... with NUL separating the elements (-z)
                #     ... and eliminate duplicates (-u)
                #   then replace the NUL bytes with line breaks
                #   allow the shell to split on those line breaks
                #   and chuck the resulting chunks into $1, $2, etc
                set -- $(printf '%s\0' "$a" "$b" "$c" "$d" | sort -z -u | tr "\0" "\n")

                # only if the current selection of elements consisted of four
                # different ones (remember we eliminated duplicates):
                if [ $# -eq 4 ]
                then
                    # create a directory, don't error out if it already exists (-p)
                    mkdir -p "$(printf '%s' "$@")"
                fi
            done
        done
    done
done

Not very efficient (sort calls even for obvious non-candidates and multiple mkdir calls for the same directory name), but at a maximum of 94 = 6561 iterations of the inner loop and with it being a single-use script, I don't think this is worth spending much time on optimisation.


Edit:
Benchmark on a Xeon E3-1231v3 without mkdir:

./elemdirs.sh > /dev/null  11.66s user 1.73s system 173% cpu 7.725 total

and with it:

./elemdirs.sh > /dev/null  13.80s user 2.16s system 156% cpu 10.215 total

It produces 126 directories, the expected number of combinations with k = 4, n = 9.

| improve this answer | |
6

Using Perl and the Algorithm::Combinatorics module:

perl -MAlgorithm::Combinatorics=combinations -e '$"=""; map { mkdir "@{$_}N" } combinations([qw(Cr Hf Mo Nb Ta Ti V W Zr)], 4)'

This would create the 126 directories that you get from all combinations of four of the included words. Each directory's name will have a N at the end. The individual words will always occur in alphabetical order in the directory names due to the initial ordering of the array in the code.

As a proper Perl script:

#!/usr/bin/perl

use strict;
use warnings;

use English;
use Algorithm::Combinatorics qw(combinations);

# When interpolating a list in a string (@{$ARG} below), don't use a delimiter
local $LIST_SEPARATOR = "";

# Get all combinations, and create a directory for each combination
map { mkdir "@{$ARG}N" } combinations( [qw(Cr Hf Mo Nb Ta Ti V W Zr)], 4 );

This would run pretty much instantaneously and is easily extended to include further words or length of combinations.

You would probably be able do something pretty similar in Python...


A recursive shell implementation (just for fun, recursive shell functions are seldom very efficient):

#!/bin/sh

build_combinations () {
    set_size=$1
    shift

    if [ "$set_size" -eq 0 ]; then
        printf 'N'
    else
        for token do
            shift
            for reminder in $(build_combinations "$(( set_size - 1 ))" "$@")
            do
                printf '%s%s\n' "$token" "$reminder"
            done
        done
    fi
}

build_combinations 4 Cr Hf Mo Nb Ta Ti V W Zr | xargs mkdir

Idea from having read studog's answer and inspiration from various bits of an answer to a StackOverflow question.

Note that the saving grace of this solution is that the directory names always end with a N. The recursive stop branch outputs N rather than an empty string, which makes the whole thing work. Without it (printing an empty string or a newline), the loop with the command substitution would have nothing to loop over and there would be no output (due to the default value of the IFS variable).

| improve this answer | |
2

An improvement on @n.st's answer that takes advantage of the fact the elements are in sorted order to start with. It's also a little clearer in my opinion.

#!/bin/bash

elements=(Cr Hf Mo Nb Ta Ti V W Zr)
len=${#elements[@]}

(( a_end = len - 3 ))
(( b_end = len - 2 ))
(( c_end = len - 1 ))
(( d_end = len - 0 ))

(( a = 0 ))
while (( a < a_end )); do
   (( b = a + 1 ))
   while (( b < b_end )); do
      (( c = b + 1 ))
      while (( c < c_end )); do
         (( d = c + 1 ))
         while (( d < d_end )); do
            mkdir "${elements[$a]}${elements[$b]}${elements[$c]}${elements[$d]}"
            (( d++ ))
         done
         (( c++ ))
      done
      (( b++ ))
   done
   (( a++ ))
done

The key part every inner loop starts at the next element index from the enclosing loop. This is a pretty common pattern for generating all combinations of a list of items.

Runtime:

user@host:~/so$ time ./do.sh 

real    0m0.140s
user    0m0.085s
sys 0m0.044s

with

user@host:~/so$ ls -1d Cr* Hf* Mo* Nb* Ta* Ti* V* W* Zr* | wc -l
ls: cannot access 'V*': No such file or directory
ls: cannot access 'W*': No such file or directory
ls: cannot access 'Zr*': No such file or directory
126
| improve this answer | |
  • 1
    It looks like this would also lend itself to a recursive implementation, which would make it possible to adjust the number of components of the directory names etc. easier. I haven't seriously thought about it though. – Kusalananda Nov 29 '18 at 21:04
  • In fact it does lend itself to a recursive implementation! I thought about doing that briefly but decided that the "unrolled" version was more instructive for this particular question. – studog Nov 29 '18 at 22:13
  • Well, I made one. – Kusalananda Nov 29 '18 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.