{"id":6265,"date":"2024-03-01T00:01:33","date_gmt":"2024-03-01T08:01:33","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=6265"},"modified":"2024-03-08T13:09:55","modified_gmt":"2024-03-08T21:09:55","slug":"calculating-the-subfactorial","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=6265","title":{"rendered":"Calculating the Subfactorial"},"content":{"rendered":"

Difficulty: ★ ★ ★ ★<\/h2>\n

Calculating a factorial is a common programming exercise, often coupled with introducing the concept of recursion. Mathematically, the factorial has a twin: the subfactorial. Its calculation can be a fun programming challenge, which is the subject of this month’s Exercise.
\n
\nAs a review, a factorial is a value written as n<\/em>!. The value represents integer n<\/em> multiplied sequentially. For example, 5! is 1×2×3×4×5, which equals 120. This value is the number of permutations possible with five items.<\/p>\n

Figure 1 illustrates 3! or three factorial. It shows the number of ways to arrange three objects, which is what 3! represents.<\/p>\n

\"Three

Figure 1. The value 3! shows how many ways to arrange three objects. 3! = 6 different arrangements.<\/p><\/div>\n

The subfactorial works along similar lines. It’s written with the exclamation point before<\/em> the value: subfactorial three is !3. The subfactorial limits the arrangements so that no objects can be in the same position as in the original. Value !3 calls out all non-unique arrangements for three objects. An example is shown in Figure 2.<\/p>\n

\"\"

Figure 2. Three subfactorial (!3) shows that only two arrangements are possible when compared with the original. !3 = 2.<\/p><\/div>\n

The best explanation of the subfactorial process, also called derangement<\/em>, is found in this video<\/a> from Andy Math. Do take time to watch it, as it describes a formula you can use to calculate subfactorials. The formula is illustrated in Figure 3.<\/p>\n

\"\"

Figure 3. The equation for calculating a subfactorial.<\/p><\/div>\n

Your task for this month’s Exercise is to write code that outputs values for subfactorials !0 through !13. You can use the equation from Figure 3 as your inspiration, which is what I did. You can also check out the Derangement Wikipedia page<\/a>, which offers more formulas and mathematical mumbojumbo.<\/p>\n

Here is output from my solution, the list of subfactorial values for !0 through !13:<\/p>\n

!0 = 1
\n!1 = 0
\n!2 = 1
\n!3 = 2
\n!4 = 9
\n!5 = 44
\n!6 = 265
\n!7 = 1854
\n!8 = 14833
\n!9 = 133496
\n!10 = 1334961
\n!11 = 14684570
\n!12 = 176214841
\n!13 = 2290792932<\/code><\/p>\n

As with factorials, these subfactorials are known values, though you can’t just write a solution that outputs the results shown above. No, you must code a solution in C.<\/p>\n

Try this Exercise on your own before you check out my solution<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Also known as “derangement.” Have fun with that. 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":[3],"tags":[],"class_list":["post-6265","post","type-post","status-publish","format-standard","hentry","category-exercise"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6265","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=6265"}],"version-history":[{"count":15,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6265\/revisions"}],"predecessor-version":[{"id":6299,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6265\/revisions\/6299"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6265"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6265"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6265"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}