{"id":20127,"date":"2022-11-08T20:03:06","date_gmt":"2022-11-08T14:33:06","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/"},"modified":"2022-11-08T20:03:06","modified_gmt":"2022-11-08T14:33:06","slug":"solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/","title":{"rendered":"[Solved] Print all permutation of length k that can be formed from a set of n characters?"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

The problem is actually like counting in base sizeof(set)<\/em> on length k<\/em> (assuming the set has 10 items maximum).<\/p>\n

For instance, with a set of { 0, 1, 2 }<\/code> on length 2, you count from 00<\/code> to 22<\/code>, base 3.<\/p>\n

To solve the “one digit change only” constraint, instead of counting increasingly, do that only until the next 10th<\/sup> change. Then count decreasingly, then again increasingly etc…<\/p>\n

For instance in the example above<\/p>\n

00 -> 02 then increase the next tenth (12), then count downward\n12 -> 10 then again +10 to get 20, then go up again\n20 -> 22\n<\/code><\/pre>\n
On length 3, keep the same reasoning, change the next 10th<\/sup> then go up or down depending on the initial value of the current digit <\/p>\n
000 -> 002, 012 -> 010, 020 -> 022\n122 -> 120, 110 -> 112, 102 -> 100\n200 -> 202, 212 -> 210, 220 -> 222\n<\/code><\/pre>\n
A recursive algorithm is one approach. The function depth 0 takes care of the first (left) digit, i.e. the highest 10th<\/sup>, and count up or down depending on its current digit state. If 0<\/code>, count up, and down otherwise. For each state, before incrementing, the function calls itself recursively with the next (right) digit status (which is either 0<\/code> or the last item in the set). The maximal depth being the length k<\/em>.<\/p>\n
Keep the digits status in an array of length k<\/em>. Array is initialized to {0 ... 0}<\/code>. Give the function the index in the array (starting with 0). For each iteration, if we’re at max depth (ie i == k-1<\/code>), print the array ; otherwise call recursively the function with i+1<\/code>.<\/p>\n
Pseudo code<\/p>\n
k length of number (number of digits)\nN size of set (1 .. 10), values from 0 to N-1\nA array of size k\n\nA[0 .. k-1] = 0\n\nfunction f ( i )\nbegin\n   inc = -1 if (A[i] > 0), 1 otherwise     # Increment\n   end =  0 if (A[i] > 0), N-1 otherwise   # Max value\n   j is the counter\n\n   j = A[ i ]   # Init\n   while ( (inc<0 AND j>=end) OR (inc>0 AND j<=end) )\n   do\n        A[ i ] = j\n\n        if (i < k-1) call f ( i+1 )\n        otherwise print array A\n\n        j = j + inc\n   done\nend\n\ncall f ( 0 )\n<\/code><\/pre>\n
This what you should get for N = 3, and k = 4<\/code><\/p>\n
0000 0001 0002 0012 0011 0010 0020 0021 0022\n0122 0121 0120 0110 0111 0112 0102 0101 0100\n0200 0201 0202 0212 0211 0210 0220 0221 0222\n1222 1221 1220 1210 1211 1212 1202 1201 1200\n1100 1101 1102 1112 1111 1110 1120 1121 1122\n1022 1021 1020 1010 1011 1012 1002 1001 1000\n2000 2001 2002 2012 2011 2010 2020 2021 2022\n2122 2121 2120 2110 2111 2112 2102 2101 2100\n2200 2201 2202 2212 2211 2210 2220 2221 2222\n<\/code><\/pre>\n
Note that you should always get  Nk<\/sup> numbers…<\/p>\n
\n
This is the C code that generated the above:<\/p>\n
int a[20] = {0}; \/\/ Put here the right size instead of 20, or use #define...\nint N,k;\n\nvoid f(int i) {\n    int inc = a[i] ? -1:1;\n    int end = a[i] ? 0:N-1;\n    int j;\n\n    for(j=a[i] ; inc<0 && j>=end || inc>0 && j<=end ; j+=inc) {\n        a[i] = j;\n        if (i < k-1) f(i+1);\n        else {\n            int z;\n            for(z=0 ; z<k ; z++) printf(\"%d\", a[z]);\n            printf(\"\\n\");\n        }\n    }\n}\n<\/code><\/pre>\n
in main()<\/code> initialize N<\/code> and k<\/code> and call<\/p>\n
f(0);\n<\/code><\/pre>\n
\n
An iterative version, that does basically the same thing<\/p>\n
void fi() {\n    int z,i,inc[k];\n\n    for(i=0 ; i<k ; i++) {\n      a[i] = 0;     \/\/ initialize our array if needed\n      inc[i] = 1;   \/\/ all digits are in +1 mode\n    }\n    int p = k-1;    \/\/ p, position: start from last digit (right)\n\n    while(p >= 0) {\n        if (p == k-1) {\n            for(z=0 ; z<k ; z++) printf(\"%d\", a[z]);\n            printf(\"\\n\");\n        }\n        if (inc[p]<0 && a[p]>0 || inc[p]>0 && a[p]<N-1) {\n          a[p] += inc[p];\n          p = k-1;\n        }\n        else {\n          inc[p] = -inc[p];\n          p--;\n        }\n    }\n}\n<\/code><\/pre>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            8<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved Print all permutation of length k that can be formed from a set of n characters? <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] The problem is actually like counting in base sizeof(set) on length k (assuming the set has 10 items maximum). For instance, with a set of { 0, 1, 2 } on length 2, you count from 00 to 22, base 3. To solve the “one digit change only” constraint, instead of counting increasingly, do … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,324,2000,323,362],"class_list":["post-20127","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-c","tag-combinatorics","tag-java","tag-string"],"yoast_head":"\n[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The problem is actually like counting in base sizeof(set) on length k (assuming the set has 10 items maximum). For instance, with a set of { 0, 1, 2 } on length 2, you count from 00 to 22, base 3. To solve the “one digit change only” constraint, instead of counting increasingly, do ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-11-08T14:33:06+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Print all permutation of length k that can be formed from a set of n characters?\",\"datePublished\":\"2022-11-08T14:33:06+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/\"},\"wordCount\":278,\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"keywords\":[\"algorithm\",\"c++\",\"combinatorics\",\"java\",\"string\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/\",\"name\":\"[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\"},\"datePublished\":\"2022-11-08T14:33:06+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Print all permutation of length k that can be formed from a set of n characters?\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#website\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/wp-content\\\/uploads\\\/2021\\\/02\\\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/logo\\\/image\\\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/#\\\/schema\\\/person\\\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"contentUrl\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/wp-content\\\/litespeed\\\/avatar\\\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\\\/\\\/jassweb.com\"],\"url\":\"https:\\\/\\\/jassweb.com\\\/solved\\\/author\\\/jaspritsinghghumangmail-com\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb","og_description":"[ad_1] The problem is actually like counting in base sizeof(set) on length k (assuming the set has 10 items maximum). For instance, with a set of { 0, 1, 2 } on length 2, you count from 00 to 22, base 3. To solve the “one digit change only” constraint, instead of counting increasingly, do ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/","og_site_name":"JassWeb","article_published_time":"2022-11-08T14:33:06+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Print all permutation of length k that can be formed from a set of n characters?","datePublished":"2022-11-08T14:33:06+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/"},"wordCount":278,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","c++","combinatorics","java","string"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/","url":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/","name":"[Solved] Print all permutation of length k that can be formed from a set of n characters? - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-11-08T14:33:06+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-print-all-permutation-of-length-k-that-can-be-formed-from-a-set-of-n-characters\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Print all permutation of length k that can be formed from a set of n characters?"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1777008400","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/20127","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=20127"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/20127\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=20127"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=20127"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=20127"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}