{"entities":{"Q1104107":{"pageid":1114859,"ns":120,"title":"Item:Q1104107","lastrevid":69652212,"modified":"2026-04-13T08:28:12Z","type":"item","id":"Q1104107","labels":{"en":{"language":"en","value":"Generating t-ary trees in A-order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055068"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$37AC0A42-18C6-41F6-A888-6A32D0386969","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90f2e75c1e57f6c125e98c7c725a615d462bfba5","datavalue":{"value":{"text":"Generating t-ary trees in A-order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104107$E5C1EB63-6016-413B-ABE1-C79AADB60CAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02c4aabebc2c559fbce638a6f679bd6822db9460","datavalue":{"value":"0646.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$031519BA-1678-47BE-8B70-F03D55615DEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2a6412277d6afe90cac1141c413a8455df9cbaae","datavalue":{"value":"10.1016/0020-0190(88)90027-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$457099EB-3349-488F-982E-F7DD912141EB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bff8eada39eac67b6346d1d71e209e51bc27f61d","datavalue":{"value":{"entity-type":"item","numeric-id":293460,"id":"Q293460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$884A5DCF-3BA0-4F14-8106-04D273E6AC33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"339b00984ebe0b1464be61c60b5f04b5d69666c9","datavalue":{"value":{"entity-type":"item","numeric-id":294634,"id":"Q294634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$2A5CD771-73EA-471A-B365-39A5E3161EA3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$ED83932B-0C04-4F30-836F-788B6A2DC2C8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1104107$2945B5AB-DB5F-498E-B792-ED02F4D3E266","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"73524bf06ae174e1abc787d91dbf62119de9f952","datavalue":{"value":"Two `natural' orders have been defined on the set of t-ary trees. \\textit{S. Zaks} [Theor. Comput. Sci. 10, 63-82 (1980; Zbl 0422.05026)] referred to these orders as A-order and B-order. Many algorithms have been developed for generating binary and t-ary trees in B-order. Here we develop an algorithm for generating all t-ary trees with n nodes in (reverse) A- order, as well as ranking and unranking algorithms. The generation algorithm produces each tree in constant average time. The analysis of the generation algorithm makes use of an interesting bijection on the set of t-ary trees. The ranking algorithm runs in O(t n) time and the unranking algorithm in O(t n lg n) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$8910EB86-16D0-4FF7-9152-621E1B4B31FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$764B108E-EB8A-44A6-8DB1-EDD3F0F1805B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$477383E8-5EC0-4100-BC9A-1ECC0DE0E9D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$36431EB3-9E2F-459C-831E-618FAA60C5E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e0bf50fff146dc048a77900d88aefe9e1f1a9821","datavalue":{"value":"4055068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$2D907F27-DBD0-4DBE-B197-07B24CEAA15C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"649161d294473b02184d48743f11fa3b62303d89","datavalue":{"value":"combinatorial generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$3E1EA4D2-6C43-4057-96BB-536B1F2D9751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a222a0335908c63c05293c2e8c078d90c3877abf","datavalue":{"value":"t-ary trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$85F9C417-275E-427F-B183-E25008DA9E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"812c516bcf37c29a7b4505d854c130d5987f6a99","datavalue":{"value":"A-order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$EFC63821-51D2-4E0B-8BFC-EC14B6F48A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4c5ea33b50c23d0e8d6513edcd11693409bdf18","datavalue":{"value":"bijection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$9BB26DC7-0BAC-4B66-8F7C-9923EB4BBB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4df73210227f5dfce7acc604ba8e77684da5f9d","datavalue":{"value":"ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104107$62EFDE57-9779-4250-B4D8-392B5F80AA18","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$317AC0CA-D2B3-433F-83D3-3246C0E83A90","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5ba617fe4c1abc4fa9a7c72223d07e9f73270b01","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90027-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104107$31ED5688-5F8B-4E71-954F-6D7365763BA2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a694003df14ae056d07ca3fe1bb780f02161b51e","datavalue":{"value":"W2062675641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104107$FE138873-519A-4FD6-9559-EE26C7BC25C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7853bf93dd63a7668077029ec9cea40df9361a0","datavalue":{"value":{"entity-type":"item","numeric-id":4114762,"id":"Q4114762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$A1E57140-B0E3-4DFF-AA78-BF8AAC81A16C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$63AA3E9C-61C6-4F85-A139-067DD4F07591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd0404fb28ff40216f861bdf0a966bbd0c05f0b8","datavalue":{"value":{"entity-type":"item","numeric-id":3802638,"id":"Q3802638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$955971A7-2A5E-4CDE-A2BC-57144459A1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb3ba2fbd0cc034db5740cb22aada68aa8c0ab0f","datavalue":{"value":{"entity-type":"item","numeric-id":4167594,"id":"Q4167594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$C2743439-13BD-4428-B31C-3FFCC0D160CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73ac7928a466b14d262d6486a7dd3e7f71b62495","datavalue":{"value":{"entity-type":"item","numeric-id":1133548,"id":"Q1133548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104107$3C08330B-CE09-4B17-B275-F04C684053CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b456147f56ce01ae717969f686fac61e5069e707","datavalue":{"value":{"entity-type":"item","numeric-id":4254656,"id":"Q4254656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd71b0ddfca3f97bc20f822384a94adef3e9140c","datavalue":{"value":{"amount":"+0.9219724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$59E257E1-0999-4BD4-95F0-80FA1EF07927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f89e3c65c2b5cd64bc625c1b2e037ae95d3ac688","datavalue":{"value":{"entity-type":"item","numeric-id":1102758,"id":"Q1102758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b31116c1eb3840aa165055f4bfdeadce3a90250","datavalue":{"value":{"amount":"+0.9126121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$906EBADE-E83F-40A6-B252-48AB0494C11D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e72930b5d7eb62e71b9ccf3be9e9d917f546e2d","datavalue":{"value":{"entity-type":"item","numeric-id":3802638,"id":"Q3802638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db66f166a754be979cfbcd5b0ea1644b33ccab00","datavalue":{"value":{"amount":"+0.9012183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$034819AB-DA76-408A-AD4E-0D609B8EB43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5908d960b5178d216f13d5d9c0fc498e82dc04d2","datavalue":{"value":{"entity-type":"item","numeric-id":4019956,"id":"Q4019956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61472104d39c122f53fbbe2491ef827ff98ecfbb","datavalue":{"value":{"amount":"+0.89322054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$FC5CA95A-41B3-4565-8C77-AA5968EF3D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"886fa19e8e92c412b9323be84fcfebcf89d8be9f","datavalue":{"value":{"entity-type":"item","numeric-id":4462115,"id":"Q4462115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9afa12c2133a407a5292c04430f91be60238050","datavalue":{"value":{"amount":"+0.8897537","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$820013A4-6EBC-4B77-B624-5D5AF0D717B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78a011fe2322e1de443bbd257ed3597c88545d2e","datavalue":{"value":{"entity-type":"item","numeric-id":1978153,"id":"Q1978153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b47180b3ce6a3a3b814b6ddd4da3e86cc91f502e","datavalue":{"value":{"amount":"+0.8832037","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$8522FB99-5947-4EA1-9C99-A66F442CC7E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28f70d3a6594598d946f3a26c963aa75a49c63c2","datavalue":{"value":{"entity-type":"item","numeric-id":3741631,"id":"Q3741631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b0afcd1deffbcad0fd4c1fe0b5f82113b681b1d","datavalue":{"value":{"amount":"+0.8804419","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1104107$70DAAA19-99E4-480E-BA1D-5F9156366A7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generating t-ary trees in A-order","badges":[]}}}}}