{"entities":{"Q1330666":{"pageid":1341416,"ns":120,"title":"Item:Q1330666","lastrevid":70157520,"modified":"2026-04-13T12:49:48Z","type":"item","id":"Q1330666","labels":{"en":{"language":"en","value":"Uniform generation of forests of restricted height"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 609772"}},"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":"Q1330666$9F74967B-C803-46A4-A937-843BF8493A9D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"19115ab1c3a872abd621e92558f5a785047bfeab","datavalue":{"value":{"text":"Uniform generation of forests of restricted height","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1330666$E4D28EBE-7FE5-4EBC-AF7C-5AB0E2D5D2F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fea7f4cb0404238c71a4dbb43c199971a7086ccf","datavalue":{"value":"0804.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$E90CFD35-962D-41BD-99AC-D0E691D4D11C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6c796ebc611c716d7cdb7c58bd096ec87208bba8","datavalue":{"value":"10.1016/0020-0190(94)00054-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$DC1251B0-0F03-4611-ADA3-2B96F26C4B81","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":"Q1330666$2DE3163D-93CA-40A8-8D6F-6A10975AE512","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"71edc96fcbd008bfd3061c3ff4af97a6b34cf242","datavalue":{"value":{"time":"+1994-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1330666$32316B83-B973-428D-BF50-3F02B9BD183D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e4384319eecd1294973f910d382d96ea64dd6b11","datavalue":{"value":"Tree structures occur throughout the theory of information storage. Typically each tree node contains some data information and some pointers to other tree nodes. In most cases the number \\(k\\) of pointer fields is fixed and the structure is referred to as a \\(k\\)-way tree. More formally, a \\(k\\)-way tree can be defined as being either empty (having no nodes) or as consisting of a root node together with an ordered sequence of \\(k\\) \\(k\\)-way trees.   For developing and testing algorithms which manipulate forests it is useful to have methods for generating them in a uniform manner (so that each forest is generated with the same probability). Many methods have been given in the case of binary trees (2-way trees with one component). Some of these methods extend to \\(k\\)-way trees but there has been little previous work on uniformly generating trees of a fixed or bounded height.   This paper considers \\(k\\)-way forests of fixed size \\(n\\), height \\(h\\), and number of components \\(c\\). A generator is given for producing such forests uniformly at random thereby answering an open problem posed by Lee, Lee, and Wong. Each random forest is generated in a linear number of operations in its size. The algorithm computes a table of values in a pre-processing phase. This table occupies \\(O(hn^ 2)\\) locations and takes \\(O(hn^ 3)\\) time to produce.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$5E1B8EBF-1F87-43A5-A046-6148D33C7A6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$95B1F2E3-AA10-41EC-B6C5-974DF7289186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$4EA2EF0B-E37E-4018-A5CF-6DFADD31EEE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$4AC076DA-FB8C-43C6-8CA2-64DFD067FA37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ab2aebf0bd271fa62f8815ea6454121c1b5f6e71","datavalue":{"value":"609772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$08F40136-719A-4EFF-AEDC-BF47174142AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6302409ec09fdeadc6bb9a580f9aea6765769730","datavalue":{"value":"random generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$A5558F7B-BEDB-43F7-B2AC-D491CA9CDB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1bd7465da93426ea77250e10d8333e8ed59b611","datavalue":{"value":"design of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$CCDC4863-03D9-4FB1-87EA-DFB583D60090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$7392C9A2-C074-41A2-B53C-BEC3C502C2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$75E3DC7F-341C-478C-B4BC-0010CD1A1EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b2d33963dc85c015ba353e197645da8b8601d","datavalue":{"value":"forests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$67556160-B165-41AF-82A3-F2A391DF0C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3a64d631d5a0cd12a3e7e81e5aa7e1c7dd498bc","datavalue":{"value":"information storage","type":"string"},"datatype":"string"},"type":"statement","id":"Q1330666$8BDEA0D4-8BD8-4CC9-89D0-E1E06431CD55","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"80dbd9e1ee1a662e8742dc81383cdc725ec4b06a","datavalue":{"value":"Q62037506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$E2B6D513-A36E-4E13-9372-3CB8EC0BB915","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b568fdac40d481abc1c48bdc7b2a892581f92b24","datavalue":{"value":{"entity-type":"item","numeric-id":1111376,"id":"Q1111376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$5A739B5E-028F-4671-8F3B-3A3F3F418EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca02099175697a4b54d6c3e10f20112dbf6ee98b","datavalue":{"value":{"entity-type":"item","numeric-id":170449,"id":"Q170449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$A01D3E2E-4246-4663-B0BA-D1B57EC8D4ED","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":"Q1330666$81559C77-324D-4345-9BB3-36B46175CAF7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"358838b8d8dd67f0db3ed0fa31f21280a81f3265","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00054-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1330666$C737B457-F8E0-46AB-8C5C-25FC55FAA1EF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"40f5f153d1b254d0b4e51be92cfc8a81c858fdbb","datavalue":{"value":"W2097280289","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1330666$3700CEC7-BBF9-4BDE-B6B3-8C57011EFDFC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4421fb21e83845400298bb443b9ee1069f58fb2","datavalue":{"value":{"entity-type":"item","numeric-id":1186567,"id":"Q1186567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$D8172ABF-8926-452E-9614-3EF4E866420D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2334ce11ba310d248a36104f2280d5019dfd7f81","datavalue":{"value":{"entity-type":"item","numeric-id":3311675,"id":"Q3311675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$36BAAF42-4139-4648-B8EC-46B9E77F18F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8986161e172d965c546a046b002a91e3baa49d8","datavalue":{"value":{"entity-type":"item","numeric-id":1171885,"id":"Q1171885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$BADAD870-454C-4ED0-BB5D-93F805517E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32d3408a91dafe39318f675c342b06c78f7b1640","datavalue":{"value":{"entity-type":"item","numeric-id":3036723,"id":"Q3036723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$985F890F-0D71-42F1-86FB-80DDE7694E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0ff209a8c00e6853b2c43b2e31810805788f0","datavalue":{"value":{"entity-type":"item","numeric-id":3935355,"id":"Q3935355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$91CEB305-8516-46CC-AEAC-3A1143A9D8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eab74f36b9d8871b83f3b302e5c7535ea7ab3d5","datavalue":{"value":{"entity-type":"item","numeric-id":2365815,"id":"Q2365815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$89F3E00D-FDD8-462B-BE52-0F4BE5A956E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9558ded8a26035023f3e94a8038e87fe4effa0ca","datavalue":{"value":{"entity-type":"item","numeric-id":1064071,"id":"Q1064071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$4B0CF3A6-AAA8-4F3A-8CC9-EA46066BCB48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a792b003de9ac6f5657c0391131ebbc02b9ed305","datavalue":{"value":{"entity-type":"item","numeric-id":1214419,"id":"Q1214419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$9CFB7253-6A38-460C-B8E4-C90DC8BC0BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae7c53f2ee736446aeda9cf33d446be27cd2e88","datavalue":{"value":{"entity-type":"item","numeric-id":4302813,"id":"Q4302813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1330666$0A3EF618-32E0-46FB-BBF3-74356097ED7F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46ceb237006a525f53cd3cb431749279e07cfa1f","datavalue":{"value":{"entity-type":"item","numeric-id":675311,"id":"Q675311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b118409a90a98ad581d9480d1d00fd7b1ac265a2","datavalue":{"value":{"amount":"+0.822116494178772","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330666$7A31491E-7535-4D75-88A1-7EE31849EAE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c72365c376cd6ce0dd7d75990e2f4b09d0ffb626","datavalue":{"value":{"entity-type":"item","numeric-id":3140121,"id":"Q3140121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"227e68f830226cc07bd234ce9f0f9a09ed9e8366","datavalue":{"value":{"amount":"+0.7964259386062622","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330666$5F017FE2-0862-447E-B371-DAEF5D3F1F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d71c9285c2d6f9b98947f88404c87f06d4535168","datavalue":{"value":{"entity-type":"item","numeric-id":4302813,"id":"Q4302813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96748847e5b33dd7660f65167c3ae1593c3a474b","datavalue":{"value":{"amount":"+0.7962738871574402","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330666$7AD5694A-2F59-4311-87AE-258B9E2D8BCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6410db5ad4dcda8ba085501c63cda214f4336631","datavalue":{"value":{"entity-type":"item","numeric-id":582880,"id":"Q582880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"545f4dabcf03e5d16d5dd2236b9e574c1b46c0f2","datavalue":{"value":{"amount":"+0.793083131313324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330666$CC0D2914-163C-4E12-BAC8-128427481D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bd55e0fe18ab24ef0f40f61266829da64653912","datavalue":{"value":{"entity-type":"item","numeric-id":1313764,"id":"Q1313764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"982680aaee0adb9502c07bbfa7580f74c7ba1191","datavalue":{"value":{"amount":"+0.7834684252738953","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1330666$1B0A0F28-A815-484B-BC57-2E18AE01E976","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniform generation of forests of restricted height","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniform_generation_of_forests_of_restricted_height"}}}}}