From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: tpeplt Newsgroups: gmane.emacs.help Subject: Re: Too many permutations computed Date: Thu, 03 Aug 2023 14:23:02 -0400 Message-ID: <873510f0jd.fsf@gmail.com> References: 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="36818"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.2 (gnu/linux) Cc: To: uzibalqa Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Thu Aug 03 20:23:53 2023 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 1qRczI-0009Ki-1Q for geh-help-gnu-emacs@m.gmane-mx.org; Thu, 03 Aug 2023 20:23:52 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qRcyc-0004k8-BI; Thu, 03 Aug 2023 14:23:10 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qRcyZ-0004h9-RZ for help-gnu-emacs@gnu.org; Thu, 03 Aug 2023 14:23:07 -0400 Original-Received: from mail-qk1-x730.google.com ([2607:f8b0:4864:20::730]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1qRcyX-0004Xb-A6 for help-gnu-emacs@gnu.org; Thu, 03 Aug 2023 14:23:07 -0400 Original-Received: by mail-qk1-x730.google.com with SMTP id af79cd13be357-76ce66110edso48176685a.0 for ; Thu, 03 Aug 2023 11:23:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1691086984; x=1691691784; h=content-transfer-encoding:mime-version:user-agent:message-id :in-reply-to:date:references:subject:cc:to:from:from:to:cc:subject :date:message-id:reply-to; bh=0h/FtOJhr16F77nw/0EO71uJt+4PQasYOks4l0ZiBIY=; b=SHEweH78/kNrVFRd5cfBAhm3VMiBdHbaZfDqVISkhGutaYRhVrr8GdYtWIf/HiPlvT T2VBO36zLjotoCdMOy9Yy+HPX697qEniH2qz1lbARR0eafBv74y9NDlcCfp8WGjLup/B xTP8skh1f/3yBZcyWEyjtwTKQ27bUSF2hVizTG7AN9GfCTnKgkF4g2hYmfivm9hZ4/X4 x1laKa68stW8cdowDFoAP5s680mvyAXQhNBAkNVZM2N5qUs3ZIak9+SPf1+DwTjVPF0d kjTExL4iRXaOkbpWW6P6egUcrT/noqgHXbT8jXFqrdnuUPWrW49GOMekBmcFeP02jAaa ZtEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691086984; x=1691691784; h=content-transfer-encoding:mime-version:user-agent:message-id :in-reply-to:date:references:subject:cc:to:from:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=0h/FtOJhr16F77nw/0EO71uJt+4PQasYOks4l0ZiBIY=; b=F8eY3Tw1p2YoaekygpOgU6GV5vAC6mG69+ROi5qrLMX8ss1db5c/6GYolxxjAUIOZR 9hYYre7i1ERi2I8B43eqdhGw0kR0a+YabmC4CkbdCtvzMnL7wDp1cbXm/qpNYMbwpmVi 47Vk9eXsFxyjr3MIIDXRt0oH2Tlh0+Y3jESLhLLhp1GXX/xM7NoMLmG5CS29QQP3Fwxz M/zk/L1aOVOdwttmknDZclAdq7I7jgdQu4OQ3lpR4Gf9877AWNcm6yrQfZDmSDNBe5j4 8BuaPo9nq+Ri1flT/TB3A61hltCMevLfx1KS8WPahmlDLju71hC+p+Q/8sDaPfXE3JZ8 a0IA== X-Gm-Message-State: ABy/qLbaa/M7E7ShQhPgDYHx90Q5yVtkEWqgPGCI/vnAx3HFvHB1s1mQ PhPegweq2kfLSM/KOcRijj4= X-Google-Smtp-Source: APBJJlGWapj5J4NGu3Nw7UohTh7T2XxtYx07joQENqx5KMLr1zmOxU8upGrzANoPh4G+/Zc4c+RZyw== X-Received: by 2002:a05:620a:702:b0:76c:ce1d:d600 with SMTP id 2-20020a05620a070200b0076cce1dd600mr4972778qkc.0.1691086983857; Thu, 03 Aug 2023 11:23:03 -0700 (PDT) Original-Received: from t530.local ([2600:8806:a821:2b00::123a]) by smtp.gmail.com with ESMTPSA id x16-20020a05620a14b000b00767d47eb29bsm87528qkj.119.2023.08.03.11.23.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Aug 2023 11:23:03 -0700 (PDT) In-Reply-To: (uzibalqa@proton.me's message of "Tue, 01 Aug 2023 18:45:08 +0000") Received-SPF: pass client-ip=2607:f8b0:4864:20::730; envelope-from=tpeplt@gmail.com; helo=mail-qk1-x730.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-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:144574 Archived-At: uzibalqa writes: > I have implemented the computations of permutations of a string using the= heap algorithm. > 1. Here are the relevant lines of the algorithm* that you cited: > // Initially k =3D length(A) > generate(k - 1, A) > > // Generate permutations for k-th swapped with each k-1 initial > for i :=3D 0; i < k-1; i +=3D 1 do Note that in the =E2=80=98for=E2=80=99 statement, the condition is i < k-1.= This is due to indexing starting at zero, i :=3D 0, so indexing is from zero to length - 1. In your procedure, you have indexing ranging from zero to length: > (while (< j h)... When this is changed to (while (< j (1- h))..., the procedure works correctly. *Heap=E2=80=99s Algorithm is named after B.R. Heap, rather than for =E2=80= =98heap=E2=80=99 or =E2=80=98the heap=E2=80=99. Here are some additional notes, but it should be possible to ignore them and simply make the change above to get your procedure to work. 2. Your procedure contains the following expression that does not appear to do anything so it might as well be deleted. > (if (null result) (setq result '())) Here is the complete listing of your procedure with the changes listed, above: (defun permute-strg-heap (strg h result) "Collect permutations of string STRG of length H into list RESULT. Use Heap=E2=80=99s Algorithm for computing all permutations." (if (=3D h 1) (progn (push (copy-sequence strg) result) ; Output the permutation (message "%s" strg)) =20=20=20=20 (progn (setq result (permute-strg-heap strg (1- h) result)) (let ((j 0)) (while (< j (1- h)) ;; Generate permutations for i-th swapped with each i-1 initial ;; Swap choice based upon h (even or odd) (if (evenp h) (swap-chars strg j (1- h)) (swap-chars strg 0 (1- h))) (setq result (permute-strg-heap strg (1- h) result)) (setq j (1+ j)))))) result) 3. No definition of the procedure =E2=80=98swap-chars=E2=80=99 was included= in your post. Here is a simple (destructive) one that works with your procedure: (defun swap-chars (str p q) "Swap characters at indices P and Q in string STR. This is destructive, that is, the value of STR is changed/lost." (let ((tmp (elt str p))) (aset str p (elt str q)) (aset str q tmp))) (setq my-string "abc") my-string =3D> "abc" (swap-chars my-string 0 2) my-string =3D> "cba" 4. A wrapper procedure could be added for safety and convenience. (defun permute (strg) "Generate a list of all permutations of the characters in string STRG." (if (string-empty-p strg) (list strg) (permute-strg-heap strg (length strg) '()))) (permute "") =3D> ("") (permute "a") =3D> ("a") (permute "ab") =3D> ("ba" "ab") (permute "abc") =3D> ("cba" "bca" "acb" "cab" "bac" "abc") This procedure will protect against empty strings that could lead to a run-time error. And it eliminates the need for the user to compute (or make a mistake) the string=E2=80=99s length or to enter the constant '(). --