{"id":1781,"date":"2016-02-27T00:01:32","date_gmt":"2016-02-27T08:01:32","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1781"},"modified":"2016-02-13T10:25:17","modified_gmt":"2016-02-13T18:25:17","slug":"permutations","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1781","title":{"rendered":"Permutations"},"content":{"rendered":"

In his 1953 short story, The Nine Billion Names of God<\/a><\/em>, Arthur C. Clarke writes of Tibetan llamas who seek to know all the names of God. They’ve been writing down the names for centuries, but upon the advent of the computer, they enlist western science to help them finish the task in days. You can complete the same task with your computer and the C programming language, but in hours instead of days.
\n
\nIn the story, Clarke cites the algorithm for printing out all the possible name combinations. Rather than just spit out names AAAAAAAAA<\/code> through ZZZZZZZZZ<\/code>, some rules are added to eliminate repetitive letters and other stipulations made by the monks.<\/p>\n

The task of generating such output is accomplished easily in any computer language: Use nested loops to generate permutations of AAAAAAAAA<\/code> through ZZZZZZZZZ<\/code>. The greater the number of characters, the long it takes the program to run. If you display the results, the program runs longer. Printing takes longest.<\/p>\n

A permutation<\/em> includes all possible results of a series such as AAAAAAAAA<\/code> through ZZZZZZZZZ<\/code>. A combination<\/em> is limited to only certain results. So in The Nine Billion Names of God<\/em>, the programmers generate combinations.<\/p><\/blockquote>\n

In the following code, three nested for<\/em> loops generate all permutations of aaa<\/code> through zzz<\/code>, what I like to call the TLA list, for Three Letter Acronyms:<\/p>\n

\r\n#include <stdio.h>\r\n\r\nint main()\r\n{\r\n    char tla[4] = \"\\0\";\r\n\r\n    for(tla[0]='a';tla[0]<='z';tla[0]++)\r\n        for(tla[1]='a';tla[1]<='z';tla[1]++)\r\n            for(tla[2]='a';tla[2]<='z';tla[2]++)\r\n                printf(\"%s \",tla);\r\n    putchar('\\n');\r\n\r\n    return(0);\r\n}<\/pre>\n
The char<\/em> array tla[]<\/code> at Line 5 is initialized to a null string, which ensures that a null character (\\0<\/code>) terminates the string.<\/p>\n
In addition to holding the output, tla[]<\/code>‘s elements are also used as variables in the for<\/em> loops. That makes the for<\/em> statements look a bit complex.<\/p>\n
Each for<\/em> loop spins from the letter 'a'<\/code> through 'z'<\/code>, inclusive, which is why the <=<\/code> operator is used.<\/p>\n
At Line 10, the printf()<\/em> statement displays each result. Then a final newline is displayed at Line 11, then the program quits.<\/p>\n
The output is all one line of text, from aaa<\/code> through zzz<\/code>, and on a modern computer the code takes only a few milliseconds to run.<\/p>\n
You can increase the number of characters in the permutation by adding another nested for<\/em> loop. That addition increases the time the program takes to run: On my system, the 3-character TLA program ran in 0.011 seconds, but the 4-character TLA program took 0.074 seconds. Adding a fifth character increased the program’s runtime to 1.941 seconds.<\/p>\n
As a challenge, a sort-of mini-Exercise, modify the code so that it doesn’t generate a single line of text as output; add code that spits out a newline after each 20th TLA is displayed. Please try this Exercise on your own; click here<\/a> to view my solution, though many solutions are possible.<\/p>\n","protected":false},"excerpt":{"rendered":"
Use nested for<\/em> loops to generate all possible combinations of letters. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1781","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1781","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1781"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1781\/revisions"}],"predecessor-version":[{"id":1791,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1781\/revisions\/1791"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1781"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1781"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1781"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}