All permutations with given characteristics

Functionality to enumerate permutations given different characteristics. In the following, n is assumed to be a non-negative integer. Permutations, in general, are coerced to cycle form.

allperms(n) returns all \(n!\) permutations of \([n]\).
allcycn() returns all \((n-1)!\) permutations of \([n]\) comprising a single cycle of length \(n\).
allcyc(s) returns all single-cycle permutations of set \(s\). If \(s\) has a repeated value, an opaque error message is returned.
allpermslike(o) takes a length-one vector o of permutations and returns a vector comprising permutations with the same shape and cycle sets as it argument.
some_perms_shape(part) takes an integer partition part, as in a set of non-negative integers, and returns a vector comprising every permutation of size sum(part) with shape part that has its cycles in increasing order.
all_cyclic_shuffles(u) takes a permutation u and returns a vector comprising of all permutations with the same shape and cycle sets. It is vectorized so that argument u may be a vector of permutations.
all_perms_shape(p) takes a permutation p and returns a vector of all permutations of size sum(p) and shape p.

Usage

allperms(n)
allcycn(n)
allcyc(s)
allpermslike(o)
some_perms_shape(shape)
all_cyclic_shuffles(o)
all_perms_shape(shape)

Arguments

shape: A set of strictly positive integers, interpreted as the shape of a partition
s: A set of strictly positive integers, interpreted as a set on which permutations are defined
n: The size of the permutation
o: A vector of permutations, coerced to cycle form. Function allpermslike() considers only the first element

Details

Function allperms() is very basic (the idiom is word(t(partitions::perms(n)))) but is here for completeness.

Author

Robin K. S. Hankin

References

M. C. Er 1989 “Efficient enumeration of cyclic permutations in situ”. International Journal of Computer Mathematics, volume 29:2-4, pp121-129.

Note

Function allcyc() is taken directly from Er's “fine-tuned” algorithm. It should really be implemented in C as part of the partitions package but I have not yet got round to this.

Examples


allperms(5)
#>   [1] ()        (45)      (34)      (345)     (354)     (35)      (23)     
#>   [8] (23)(45)  (234)     (2345)    (2354)    (235)     (243)     (2453)   
#>  [15] (24)      (245)     (24)(35)  (2435)    (2543)    (253)     (254)    
#>  [22] (25)      (2534)    (25)(34)  (12)      (12)(45)  (12)(34)  (12)(345)
#>  [29] (12)(354) (12)(35)  (123)     (123)(45) (1234)    (12345)   (12354)  
#>  [36] (1235)    (1243)    (12453)   (124)     (1245)    (124)(35) (12435)  
#>  [43] (12543)   (1253)    (1254)    (125)     (12534)   (125)(34) (132)    
#>  [50] (132)(45) (1342)    (13452)   (13542)   (1352)    (13)      (13)(45) 
#>  [57] (134)     (1345)    (1354)    (135)     (13)(24)  (13)(245) (1324)   
#>  [64] (13245)   (13524)   (135)(24) (13)(254) (13)(25)  (13254)   (1325)   
#>  [71] (134)(25) (13425)   (1432)    (14532)   (142)     (1452)    (142)(35)
#>  [78] (14352)   (143)     (1453)    (14)      (145)     (14)(35)  (1435)   
#>  [85] (1423)    (14523)   (14)(23)  (145)(23) (14)(235) (14235)   (14253)  
#>  [92] (143)(25) (14)(253) (14325)   (14)(25)  (1425)    (15432)   (1532)   
#>  [99] (1542)    (152)     (15342)   (152)(34) (1543)    (153)     (154)    
#> [106] (15)      (1534)    (15)(34)  (15423)   (1523)    (154)(23) (15)(23) 
#> [113] (15234)   (15)(234) (153)(24) (15243)   (15324)   (15)(243) (1524)   
#> [120] (15)(24) 
#> [coerced from word form]

allcycn(5)
#>  [1] (12345) (12354) (12453) (12435) (12534) (12543) (13452) (13542) (13245)
#> [10] (13524) (13425) (13254) (14523) (14235) (14532) (14352) (14253) (14325)
#> [19] (15234) (15423) (15324) (15243) (15342) (15432)
#> [coerced from word form]

allcyc(c(5,6,8,3))
#> [1] (3568) (3856) (3658) (3586) (3685) (3865)

allpermslike(as.cycle("(12)(34)(5678)"))
#> [1] (12)(34)(5678) (12)(34)(5687) (12)(34)(5786) (12)(34)(5768) (12)(34)(5867)
#> [6] (12)(34)(5876)
allpermslike(rgivenshape(c(1,1,3,4)))
#>  [1] (258)(3974) (285)(3974) (258)(3947) (285)(3947) (258)(3749) (285)(3749)
#>  [7] (258)(3794) (285)(3794) (258)(3497) (285)(3497) (258)(3479) (285)(3479)
some_perms_shape(c(2,2,4))
#>   [1] (1278)(35)(46) (1278)(36)(45) (1278)(34)(56) (1238)(45)(67) (1238)(47)(56)
#>   [6] (1238)(46)(57) (1237)(48)(56) (1237)(45)(68) (1237)(46)(58) (1236)(48)(57)
#>  [11] (1236)(47)(58) (1236)(45)(78) (1234)(58)(67) (1234)(57)(68) (1234)(56)(78)
#>  [16] (1235)(48)(67) (1235)(47)(68) (1235)(46)(78) (1248)(35)(67) (1248)(37)(56)
#>  [21] (1248)(36)(57) (1247)(38)(56) (1247)(35)(68) (1247)(36)(58) (1246)(38)(57)
#>  [26] (1246)(37)(58) (1246)(35)(78) (1245)(38)(67) (1245)(37)(68) (1245)(36)(78)
#>  [31] (1258)(36)(47) (1258)(37)(46) (1258)(34)(67) (1257)(38)(46) (1257)(36)(48)
#>  [36] (1257)(34)(68) (1256)(38)(47) (1256)(37)(48) (1256)(34)(78) (1268)(35)(47)
#>  [41] (1268)(37)(45) (1268)(34)(57) (1267)(38)(45) (1267)(35)(48) (1267)(34)(58)
#>  [46] (1378)(25)(46) (1378)(24)(56) (1378)(26)(45) (1348)(25)(67) (1348)(26)(57)
#>  [51] (1348)(27)(56) (1347)(28)(56) (1347)(26)(58) (1347)(25)(68) (1346)(28)(57)
#>  [56] (1346)(25)(78) (1346)(27)(58) (1345)(28)(67) (1345)(26)(78) (1345)(27)(68)
#>  [61] (1358)(26)(47) (1358)(24)(67) (1358)(27)(46) (1357)(28)(46) (1357)(24)(68)
#>  [66] (1357)(26)(48) (1356)(28)(47) (1356)(24)(78) (1356)(27)(48) (1368)(25)(47)
#>  [71] (1368)(24)(57) (1368)(27)(45) (1367)(28)(45) (1367)(24)(58) (1367)(25)(48)
#>  [76] (1478)(25)(36) (1478)(26)(35) (1478)(23)(56) (1458)(26)(37) (1458)(27)(36)
#>  [81] (1458)(23)(67) (1457)(28)(36) (1457)(26)(38) (1457)(23)(68) (1456)(28)(37)
#>  [86] (1456)(27)(38) (1456)(23)(78) (1468)(25)(37) (1468)(27)(35) (1468)(23)(57)
#>  [91] (1467)(28)(35) (1467)(25)(38) (1467)(23)(58) (1578)(26)(34) (1578)(24)(36)
#>  [96] (1578)(23)(46) (1568)(27)(34) (1568)(24)(37) (1568)(23)(47) (1567)(28)(34)
#> [101] (1567)(24)(38) (1567)(23)(48) (1678)(25)(34) (1678)(24)(35) (1678)(23)(45)
#> [106] (14)(2378)(56) (15)(2378)(46) (16)(2378)(45) (16)(2348)(57) (15)(2348)(67)
#> [111] (17)(2348)(56) (16)(2347)(58) (18)(2347)(56) (15)(2347)(68) (15)(2346)(78)
#> [116] (18)(2346)(57) (17)(2346)(58) (16)(2345)(78) (18)(2345)(67) (17)(2345)(68)
#> [121] (14)(2358)(67) (16)(2358)(47) (17)(2358)(46) (14)(2357)(68) (18)(2357)(46)
#> [126] (16)(2357)(48) (14)(2356)(78) (18)(2356)(47) (17)(2356)(48) (14)(2368)(57)
#> [131] (15)(2368)(47) (17)(2368)(45) (14)(2367)(58) (18)(2367)(45) (15)(2367)(48)
#> [136] (16)(2478)(35) (15)(2478)(36) (13)(2478)(56) (17)(2458)(36) (16)(2458)(37)
#> [141] (13)(2458)(67) (16)(2457)(38) (18)(2457)(36) (13)(2457)(68) (17)(2456)(38)
#> [146] (18)(2456)(37) (13)(2456)(78) (17)(2468)(35) (15)(2468)(37) (13)(2468)(57)
#> [151] (15)(2467)(38) (18)(2467)(35) (13)(2467)(58) (14)(2578)(36) (16)(2578)(34)
#> [156] (13)(2578)(46) (14)(2568)(37) (17)(2568)(34) (13)(2568)(47) (14)(2567)(38)
#> [161] (18)(2567)(34) (13)(2567)(48) (14)(2678)(35) (15)(2678)(34) (13)(2678)(45)
#> [166] (16)(25)(3478) (12)(3478)(56) (15)(26)(3478) (17)(26)(3458) (12)(3458)(67)
#> [171] (16)(27)(3458) (16)(28)(3457) (12)(3457)(68) (18)(26)(3457) (17)(28)(3456)
#> [176] (12)(3456)(78) (18)(27)(3456) (17)(25)(3468) (12)(3468)(57) (15)(27)(3468)
#> [181] (15)(28)(3467) (12)(3467)(58) (18)(25)(3467) (14)(26)(3578) (12)(3578)(46)
#> [186] (16)(24)(3578) (14)(27)(3568) (12)(3568)(47) (17)(24)(3568) (14)(28)(3567)
#> [191] (12)(3567)(48) (18)(24)(3567) (14)(25)(3678) (12)(3678)(45) (15)(24)(3678)
#> [196] (16)(23)(4578) (12)(36)(4578) (13)(26)(4578) (17)(23)(4568) (12)(37)(4568)
#> [201] (13)(27)(4568) (18)(23)(4567) (12)(38)(4567) (13)(28)(4567) (15)(23)(4678)
#> [206] (12)(35)(4678) (13)(25)(4678) (14)(23)(5678) (12)(34)(5678) (13)(24)(5678)
all_cyclic_shuffles(cyc_len(3:5))
#>  [1] (123)   (132)   (1234)  (1243)  (1342)  (1324)  (1423)  (1432)  (12345)
#> [10] (12354) (12453) (12435) (12534) (12543) (13452) (13542) (13245) (13524)
#> [19] (13425) (13254) (14523) (14235) (14532) (14352) (14253) (14325) (15234)
#> [28] (15423) (15324) (15243) (15342) (15432)

all_perms_shape(c(2,2,3))
#>   [1] (127)(35)(46) (172)(35)(46) (127)(36)(45) (172)(36)(45) (127)(34)(56)
#>   [6] (172)(34)(56) (126)(37)(45) (162)(37)(45) (126)(35)(47) (162)(35)(47)
#>  [11] (126)(34)(57) (162)(34)(57) (123)(47)(56) (132)(47)(56) (123)(46)(57)
#>  [16] (132)(46)(57) (123)(45)(67) (132)(45)(67) (124)(37)(56) (142)(37)(56)
#>  [21] (124)(36)(57) (142)(36)(57) (124)(35)(67) (142)(35)(67) (125)(37)(46)
#>  [26] (152)(37)(46) (125)(36)(47) (152)(36)(47) (125)(34)(67) (152)(34)(67)
#>  [31] (137)(25)(46) (173)(25)(46) (137)(24)(56) (173)(24)(56) (137)(26)(45)
#>  [36] (173)(26)(45) (136)(27)(45) (163)(27)(45) (136)(24)(57) (163)(24)(57)
#>  [41] (136)(25)(47) (163)(25)(47) (134)(27)(56) (143)(27)(56) (134)(25)(67)
#>  [46] (143)(25)(67) (134)(26)(57) (143)(26)(57) (135)(27)(46) (153)(27)(46)
#>  [51] (135)(24)(67) (153)(24)(67) (135)(26)(47) (153)(26)(47) (147)(25)(36)
#>  [56] (174)(25)(36) (147)(26)(35) (174)(26)(35) (147)(23)(56) (174)(23)(56)
#>  [61] (146)(27)(35) (164)(27)(35) (146)(25)(37) (164)(25)(37) (146)(23)(57)
#>  [66] (164)(23)(57) (145)(27)(36) (154)(27)(36) (145)(26)(37) (154)(26)(37)
#>  [71] (145)(23)(67) (154)(23)(67) (157)(26)(34) (175)(26)(34) (157)(24)(36)
#>  [76] (175)(24)(36) (157)(23)(46) (175)(23)(46) (156)(27)(34) (165)(27)(34)
#>  [81] (156)(24)(37) (165)(24)(37) (156)(23)(47) (165)(23)(47) (167)(25)(34)
#>  [86] (176)(25)(34) (167)(24)(35) (176)(24)(35) (167)(23)(45) (176)(23)(45)
#>  [91] (14)(237)(56) (14)(273)(56) (15)(237)(46) (15)(273)(46) (16)(237)(45)
#>  [96] (16)(273)(45) (14)(236)(57) (14)(263)(57) (17)(236)(45) (17)(263)(45)
#> [101] (15)(236)(47) (15)(263)(47) (15)(234)(67) (15)(243)(67) (17)(234)(56)
#> [106] (17)(243)(56) (16)(234)(57) (16)(243)(57) (14)(235)(67) (14)(253)(67)
#> [111] (17)(235)(46) (17)(253)(46) (16)(235)(47) (16)(253)(47) (16)(247)(35)
#> [116] (16)(274)(35) (15)(247)(36) (15)(274)(36) (13)(247)(56) (13)(274)(56)
#> [121] (15)(246)(37) (15)(264)(37) (17)(246)(35) (17)(264)(35) (13)(246)(57)
#> [126] (13)(264)(57) (16)(245)(37) (16)(254)(37) (17)(245)(36) (17)(254)(36)
#> [131] (13)(245)(67) (13)(254)(67) (14)(257)(36) (14)(275)(36) (16)(257)(34)
#> [136] (16)(275)(34) (13)(257)(46) (13)(275)(46) (14)(256)(37) (14)(265)(37)
#> [141] (17)(256)(34) (17)(265)(34) (13)(256)(47) (13)(265)(47) (14)(267)(35)
#> [146] (14)(276)(35) (15)(267)(34) (15)(276)(34) (13)(267)(45) (13)(276)(45)
#> [151] (16)(25)(347) (16)(25)(374) (12)(347)(56) (12)(374)(56) (15)(26)(347)
#> [156] (15)(26)(374) (15)(27)(346) (15)(27)(364) (12)(346)(57) (12)(364)(57)
#> [161] (17)(25)(346) (17)(25)(364) (16)(27)(345) (16)(27)(354) (12)(345)(67)
#> [166] (12)(354)(67) (17)(26)(345) (17)(26)(354) (14)(26)(357) (14)(26)(375)
#> [171] (12)(357)(46) (12)(375)(46) (16)(24)(357) (16)(24)(375) (14)(27)(356)
#> [176] (14)(27)(365) (12)(356)(47) (12)(365)(47) (17)(24)(356) (17)(24)(365)
#> [181] (14)(25)(367) (14)(25)(376) (12)(367)(45) (12)(376)(45) (15)(24)(367)
#> [186] (15)(24)(376) (16)(23)(457) (16)(23)(475) (12)(36)(457) (12)(36)(475)
#> [191] (13)(26)(457) (13)(26)(475) (17)(23)(456) (17)(23)(465) (12)(37)(456)
#> [196] (12)(37)(465) (13)(27)(456) (13)(27)(465) (15)(23)(467) (15)(23)(476)
#> [201] (12)(35)(467) (12)(35)(476) (13)(25)(467) (13)(25)(476) (14)(23)(567)
#> [206] (14)(23)(576) (12)(34)(567) (12)(34)(576) (13)(24)(567) (13)(24)(576)
all_perms_shape(c(2,2,1,1))  # size 6 (length-1 cycles vanish)
#>  [1] (16)(25) (16)(24) (16)(23) (16)(35) (16)(34) (16)(45) (12)(56) (12)(36)
#>  [9] (12)(35) (12)(34) (12)(46) (12)(45) (13)(26) (13)(24) (13)(25) (13)(56)
#> [17] (13)(46) (13)(45) (14)(26) (14)(25) (14)(23) (14)(36) (14)(35) (14)(56)
#> [25] (15)(26) (15)(24) (15)(23) (15)(36) (15)(34) (15)(46) (26)(35) (26)(34)
#> [33] (26)(45) (23)(56) (23)(46) (23)(45) (24)(36) (24)(35) (24)(56) (25)(36)
#> [41] (25)(34) (25)(46) (36)(45) (34)(56) (35)(46)