{"entities":{"Q1109773":{"pageid":1120522,"ns":120,"title":"Item:Q1109773","lastrevid":80308928,"modified":"2026-05-06T15:54:04Z","type":"item","id":"Q1109773","labels":{"en":{"language":"en","value":"Shortest prefix strings containing all subset permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070900"}},"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":"Q1109773$A98A36A4-6FAE-49D6-A915-4D6957D97868","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4861c45caea9dd3a6ffb734704c0c6277b6387d2","datavalue":{"value":{"text":"Shortest prefix strings containing all subset permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109773$BE699EDA-A6F9-42C8-9E92-83093BEE4B41","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cc52b314f6f1e516eb73eb8f1bed359ef6dde346","datavalue":{"value":"0656.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109773$29A51F83-9FB9-496B-A134-674A4107C195","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c7813bfecf9e41d86425e1a7f4711a27d8d3363","datavalue":{"value":"10.1016/0012-365X(87)90193-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109773$EB6B9851-52B2-4ABA-9C6D-54E25802FBC3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26746dbc33f3758ff0c811c5b77df5443ce35694","datavalue":{"value":{"entity-type":"item","numeric-id":672747,"id":"Q672747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$BC461EF9-0E88-430D-9A27-F2F7EEEF8C41","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$430A8479-7EC1-4A03-84C9-655FB560F889","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1109773$3851592C-167C-4666-8A6A-5441CFE7095E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d9f1dfda580368a3d359f529700cde369304aa1","datavalue":{"value":"\\textit{D. E. Knuth} poses the following problem: What is the length of the shortest string consisting of elements of \\(\\{\\) 1,2,...,n\\(\\}\\) that contains all permutations of the set as subsequences? [\\textit{V. Chv\u00e1tal, D. A. Klarner} and \\textit{D. E. Knuth}, Selected combinatorial research problems, Technical report CS-72-292, Stanford University (1972)]. In the paper under review, the author studies an incremental variation on this problem first proposed by \\textit{P. J. Koutas} and \\textit{T. C. Hu} [Discrete Math. 11, 125-132 (1975; Zbl 0296.05004)]. The problem can be viewed as follows: For \\(k=1\\) one needs n distinct digits to find each of the n possible permutations. In going from k to \\(k+1\\), one starts with a string containing all k-element permutations as subsequences, and one adds as few digits as possible to the end of the string so that the new string contains all \\((k+1)\\)-element permutations.    The author gives a new construction that given shorter strings then the best previous construction. The lower bound for the number of digits added in successive suffixes is also presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109773$B12FD621-C890-4BDA-8DD5-8DB220C18954","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109773$FE48A90A-BC62-49FC-97A0-5E34A7FE49F4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"120c8cf042354ba3d949c81188004f22470f6427","datavalue":{"value":"4070900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109773$F9F14936-93A3-475C-A924-E55FFB4E88B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f652530d42929702e40148b87d683fd06b440246","datavalue":{"value":"sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109773$7DBD3BC4-08F0-4379-B04C-7202167498CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fc7ac30a94024ce002aabf216db13396e3c2061","datavalue":{"value":"shortest string","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109773$163CD245-872D-4C10-9A71-1A22992C45C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4ce0d50ef2d3fddc856fbf9944536f0e151c35f","datavalue":{"value":"permutations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109773$2D72B087-1848-4693-A02E-A22DFD33A780","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":"Q1109773$D5EBFBDF-BDB2-40F0-BFFE-236471920C5D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1020400327a4778d79dbc31460af967bc5f110ac","datavalue":{"value":{"entity-type":"item","numeric-id":1221115,"id":"Q1221115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$510ED8FB-055B-4B29-884B-DB605E0DC5D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14b050c3b00bf29f96253e81836a09ccf59cfcde","datavalue":{"value":{"entity-type":"item","numeric-id":1166523,"id":"Q1166523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$F9B17F62-655A-4E2F-86E7-9AD334156AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c11dbebf25940a94e6266888d1cae1f7290b895","datavalue":{"value":{"entity-type":"item","numeric-id":4103535,"id":"Q4103535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$A697E1B2-22C7-46F3-903F-27A0329E2566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f09adf87a56fcda9f3bd01c6517cfcdc43893226","datavalue":{"value":{"entity-type":"item","numeric-id":1228615,"id":"Q1228615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$F409292D-8110-4100-B1CF-ABDFBBA54E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9688cc92a582c03d80b6899b9dbfcdac47ae136","datavalue":{"value":{"entity-type":"item","numeric-id":5905688,"id":"Q5905688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$90A8D39A-A3F5-470F-991C-681D92FD6D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"818f7075feb21becc1a7eaedfab4426485bce0fa","datavalue":{"value":{"entity-type":"item","numeric-id":1835672,"id":"Q1835672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109773$7E87DC83-BC47-4B46-8A11-83CA5BF67783","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20182cdc73e2456eaaa653aceab13d0a2bfa7d07","datavalue":{"value":{"entity-type":"item","numeric-id":3495361,"id":"Q3495361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bd152ec87e5b68b63d5ab6309ddae0748cbc6ee","datavalue":{"value":{"amount":"+0.8644449710845947","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":"Q1109773$47DD9AB6-9423-468E-9ABB-21EDABD929CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19e6de9d9f8286b29f771031997ae8c771f22951","datavalue":{"value":{"entity-type":"item","numeric-id":1944962,"id":"Q1944962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0c47b5ae25d296e9a7300aae3011fbe2c159c00","datavalue":{"value":{"amount":"+0.8611046075820923","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":"Q1109773$965DDB0C-AD5C-4ED6-8E08-30D24E961EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"385d8b58e8c65869f74b6c32568c7672763b9614","datavalue":{"value":{"entity-type":"item","numeric-id":5144492,"id":"Q5144492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"537c3586e8a3efbe3fffed0568f35dd3bf0a689b","datavalue":{"value":{"amount":"+0.8066443800926208","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":"Q1109773$6B718519-8CE9-44E2-8F09-AC04212550FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c4b3a5d66211cd695c4fa61a846ead29b2208a3","datavalue":{"value":{"entity-type":"item","numeric-id":1953339,"id":"Q1953339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"638c1167dbaa02406c5a1119013577e10f789ecf","datavalue":{"value":{"amount":"+0.7756611108779907","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":"Q1109773$B81A6249-3F6B-4FB6-8160-4D4EE1B4A218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75ef07cbd3c79df93a23b4a77c2ac98dc769fd07","datavalue":{"value":{"entity-type":"item","numeric-id":389216,"id":"Q389216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"680edeef81ee64c3cd7104fee16516e687da2cce","datavalue":{"value":{"amount":"+0.7587152719497681","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":"Q1109773$D5DA2793-4D73-45EE-9061-6043902BFA7E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Shortest prefix strings containing all subset permutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Shortest_prefix_strings_containing_all_subset_permutations"}}}}}