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.

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

allperms(n) returns all \(n!\) permutations of \([n]\). It is very basic (the idiom is word(t(partitions::perms(n)))) but is here for completeness.
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.

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(3,3))    # size 6
#>  [1] (126)(345) (125)(346) (123)(456) (124)(356) (136)(245) (135)(246)
#>  [7] (134)(256) (146)(235) (145)(236) (156)(234)
some_perms_shape(c(3,3,1))  # size 7 (length-1 cycles vanish)
#>  [1] (127)(356) (127)(345) (127)(346) (127)(456) (126)(357) (126)(347)
#>  [7] (126)(345) (126)(457) (123)(567) (123)(467) (123)(457) (123)(456)
#> [13] (124)(367) (124)(357) (124)(356) (124)(567) (125)(367) (125)(347)
#> [19] (125)(346) (125)(467) (137)(256) (137)(245) (137)(246) (137)(456)
#> [25] (136)(247) (136)(245) (136)(257) (136)(457) (134)(257) (134)(256)
#> [31] (134)(267) (134)(567) (135)(247) (135)(246) (135)(267) (135)(467)
#> [37] (147)(256) (147)(235) (147)(236) (147)(356) (146)(257) (146)(237)
#> [43] (146)(235) (146)(357) (145)(267) (145)(237) (145)(236) (145)(367)
#> [49] (157)(246) (157)(236) (157)(234) (157)(346) (156)(247) (156)(237)
#> [55] (156)(234) (156)(347) (167)(245) (167)(235) (167)(234) (167)(345)
#> [61] (237)(456) (236)(457) (234)(567) (235)(467) (247)(356) (246)(357)
#> [67] (245)(367) (257)(346) (256)(347) (267)(345)

all_cyclic_shuffles(as.cycle(1:3) + as.cycle(4:7))
#>  [1] (123)(4567) (132)(4567) (123)(4576) (132)(4576) (123)(4675) (132)(4675)
#>  [7] (123)(4657) (132)(4657) (123)(4756) (132)(4756) (123)(4765) (132)(4765)
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)