From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Yuri Khan Newsgroups: gmane.emacs.help Subject: Re: puzzle with string permutations [photo] Date: Tue, 7 Jun 2022 23:09:36 +0700 Message-ID: References: <87r141rn8n.fsf@dataswamp.org> <87wndtrlpg.fsf@mbork.pl> <87k09ssycf.fsf@dataswamp.org> <87fskgsy4c.fsf@dataswamp.org> <87bkv4sxnu.fsf@dataswamp.org> <87bkv4r35k.fsf@dataswamp.org> <8735ggr1z0.fsf@dataswamp.org> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34409"; mail-complaints-to="usenet@ciao.gmane.io" To: help-gnu-emacs Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Tue Jun 07 18:21:09 2022 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nybx6-0008ho-H5 for geh-help-gnu-emacs@m.gmane-mx.org; Tue, 07 Jun 2022 18:21:08 +0200 Original-Received: from localhost ([::1]:33620 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nybx5-0004bK-5M for geh-help-gnu-emacs@m.gmane-mx.org; Tue, 07 Jun 2022 12:21:07 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:51292) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nybmB-0000Xd-7r for help-gnu-emacs@gnu.org; Tue, 07 Jun 2022 12:09:51 -0400 Original-Received: from mail-yb1-xb2f.google.com ([2607:f8b0:4864:20::b2f]:33457) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nybm8-0004og-Ry for help-gnu-emacs@gnu.org; Tue, 07 Jun 2022 12:09:50 -0400 Original-Received: by mail-yb1-xb2f.google.com with SMTP id s39so4372225ybi.0 for ; Tue, 07 Jun 2022 09:09:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :content-transfer-encoding; bh=YzfJcawyU8CDLqYLXGsQLMpR5NUG0UHuqcWuK1OEIKg=; b=d1FV+6PDLtHcu1GXb7wNxXxg3CGIW0ONUIJiRZthHGlOeKcooafcZ+66eVWWJxZ91q QKPlv31Iqvj5zYFtgDe8HhOPNnXtVsMltD4eUU6pqXyF3dHx5P1XRC+HoXMAckWIdc95 7lDepMjNA4HrbOBx6UU0GcDt4sLHmpnOJDX0rfiFAZR0rCD78JGkDKnqrvRRQ8oGiA1Q LueOqhEaRXPpWTGRh4oo6dPg9FyfD/ERIsOl0P4ZjjKS65gcuoN8XyOL16aH2kK3Ct6Z JkfAqNihYO/8OcvEnfPLBQeCgVY/0K/TpkEvJf83AAedt+wLT99JJbWPAlITmXvEF0rm UuaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:content-transfer-encoding; bh=YzfJcawyU8CDLqYLXGsQLMpR5NUG0UHuqcWuK1OEIKg=; b=d6m7u9O2s2GoQUIc1l2DwuqbwufiolUNCdaWd9YtCQd2QvPIGl0L6vvLdlAJzo3YVp kvjKQy5fHwzg5debWgJtH6l4OsRq8/nlUw13y4sBD8BiTxx0w6G/CEtTI0Fv9X8EU+7B paBANgQGBI0BJcQ8GEt7lIwTkpBXKEVvKzCAQqiCcP+hHCi28lXXgXDmXrLalSstNABw 0T10Oqgf+WYXC46erPYmPPlMaPVDr/+uo5NWfp0sTg20Z8IuAGLKF2EaI9i7gK5SQtJw 0CpJSLluUareVEA06NsLBz/9f1GDsg1bgvvPdaviCLPM/j3DTKHxcLmb9I9On5XUmBoy 9RLw== X-Gm-Message-State: AOAM530ikrhuw9L91Tj/vJyeZZD487/l94Qzw150zeoK3K4vL43rJgyJ qSKOCKzLaRGfH7U9j0xaxx/XZCN9muI2BU7wQJgLp4OBN4o= X-Google-Smtp-Source: ABdhPJymxJky3S1+SLWAYS5gB4UY++MifB7J0qzBtlBIQMRYXP5W2lWR/AXK1DdoahLwJSpdWCvQxRLCrZDiDZGAMss= X-Received: by 2002:a25:6b47:0:b0:65c:baf6:3924 with SMTP id o7-20020a256b47000000b0065cbaf63924mr30898751ybm.485.1654618187022; Tue, 07 Jun 2022 09:09:47 -0700 (PDT) In-Reply-To: <8735ggr1z0.fsf@dataswamp.org> Received-SPF: pass client-ip=2607:f8b0:4864:20::b2f; envelope-from=yurivkhan@gmail.com; helo=mail-yb1-xb2f.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "help-gnu-emacs" Xref: news.gmane.io gmane.emacs.help:137516 Archived-At: On Tue, 7 Jun 2022 at 21:18, Emanuel Berg wrote: > It doesn't work exactly like that with strings, since for > example the scrambled word "ogod" is actually, here, treated > as > > o_1 g o_2 d > > Yet the words > > g o_1 o_2 d > g o_2 o_1 d > > are duplicates. This extension of the concept of sets is called a multiset or a bag. For each element, we also have a multiplicity. Let=E2=80=99s write it as {o= :2, g:1, d:1}. Let=E2=80=99s solve the problem: Given a multiset of letters {X_1:n_1, =E2= =80=A6, X_k:n_k}, how many distinct strings using up all of them are there? First, we treat repeating letters as if they were distinct, e.g. by numbering them as you did above: {o_1, o_2, g, d}. These are 4 letters and there are 4! =3D 24 permutations. However, every two permutations that only differ by the order of o_1 and o_2 are equivalent in our original unnumbered multiset. So we have to divide by two: 4! / 2 =3D 24 / 2 =3D 12. dgoo, dogo, doog, gdoo, godo, good, odgo, odog, ogdo, ogod, oodg, oogd. What do we do if there are three or more instances of each letter? Let=E2=80=99s consider a degenerate multiset {w:3}. If we number the instances, it=E2=80=99s {w_1, w_2, w_3} and there are 3! =3D 6 permutations= , but clearly the only distinct string is www. So it looks like we need to divide by 3! =3D 6: 3! / 3! =3D 6 / 6 =3D 1. In general, with a multiset {X_1:n_1, =E2=80=A6, X_k:n_k}, if we number eac= h letter, we get (n_1 + =E2=80=A6 + n_k)! permutations, and then we have to adjust for duplicates for each individual letter by dividing by (n_1)! =E2=80=A6 (n_k)!. n_perm =3D (n_1 + =E2=80=A6 + n_k)! / (n_1)! =E2=80=A6 (n_k)! For the above example of {o:2, g:1, d:1}: n_perm =3D (2 + 1 + 1)! / 2! 1! 1! =3D 4! / 2 1 1 =3D 24 / 2 =3D 12. (This problem was part of my exam in maths when I was applying at Novosibirsk State University, Mechanics & Maths Department, in 1997.) (You might also notice the formula is similar to that of a binomial coefficient: C_{n,k} =3D n! / k! (n-k)!. That=E2=80=99s no coincidence.)