From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: uzibalqa Newsgroups: gmane.emacs.help Subject: Too many permutations computed Date: Tue, 01 Aug 2023 18:45:08 +0000 Message-ID: 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="24248"; mail-complaints-to="usenet@ciao.gmane.io" To: uzibalqa via Users list for the GNU Emacs text editor Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Tue Aug 01 20:46:18 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 1qQuNs-00063i-Kz for geh-help-gnu-emacs@m.gmane-mx.org; Tue, 01 Aug 2023 20:46:16 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1qQuNd-00070V-BI; Tue, 01 Aug 2023 14:46:02 -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 1qQuNH-0006ut-Nj for help-gnu-emacs@gnu.org; Tue, 01 Aug 2023 14:45:40 -0400 Original-Received: from mail-4325.protonmail.ch ([185.70.43.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qQuND-0005MT-Pu for help-gnu-emacs@gnu.org; Tue, 01 Aug 2023 14:45:39 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=proton.me; s=protonmail; t=1690915525; x=1691174725; bh=MitR52+pFhnywwNEyEjeLchbDnrJi3zHkNaSJornMYs=; h=Date:To:From:Subject:Message-ID:Feedback-ID:From:To:Cc:Date: Subject:Reply-To:Feedback-ID:Message-ID:BIMI-Selector; b=AND1bJBA1WmdT4Og+H3lSV/FgsfqS6ewWANMlp8ZAiWku6OVEB2Ifol9BtaryQJsH k+0IvKv3D7i23CBFP/taM2cObbj4C8VvJdjdMZfyLiiu0lY5Xw8txoH5XNRfj97deJ Ar8Dunziluj4qiEZvk3QAPSKCJjSgGZUKQDT8R8NTYuSfSPLrENoiaXqMPjmgx7EPH Btu9kXcJkHqqZj2fjW99wjb9NiYcrcZt7j3hfCEfl6Ep8ZTifVQKXqYaPn9eztrGL3 PBRs8T4aGbyMvQl7pxrPDiHMTOz+zsYjgohHZ/8wgOnZzFiHyQ7Iztxw7gwDLwoRuF DImsp3n78x49g== Feedback-ID: 52887082:user:proton Received-SPF: pass client-ip=185.70.43.25; envelope-from=uzibalqa@proton.me; helo=mail-4325.protonmail.ch 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, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-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:144541 Archived-At: I have implemented the computations of permutations of a string using the h= eap algorithm. But I am getting repetitions, which should not happen. There could be some= problems in the=20 way the recursive calls are handled, and the result list is not being upda= ted correctly. (defun permute-strg-heap (strg h &optional result) "Generate all permutations of string STRG using recursive backtracking." (if (null result) (setq result '())) (if (=3D h 1) (progn (push (copy-sequence strg) result) ; Output the permutation (message "%s" strg)) (progn (setq result (permute-strg-heap strg (1- h) result)) ;; Generate permutations for i-th swapped with each i-1 initial (let ( (j 0) ) (while (< j h) ;; 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) This should be tho algorithm procedure generate(k : integer, A : array of any): if k =3D 1 then output(A) else // Generate permutations with k-th unaltered // 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 // Swap choice dependent on parity of k (even or odd) if k is even then swap(A[i], A[k-1]) // zero-indexed, the k-th is at k-1 else swap(A[0], A[k-1]) end if generate(k - 1, A) end for end if