برنامه چاپ جایگشت های رشته — به زبان ساده

۲۵۸۸ بازدید
آخرین به‌روزرسانی: ۱۰ تیر ۱۴۰۲
زمان مطالعه: ۴ دقیقه
برنامه چاپ جایگشت های رشته — به زبان ساده

«جایگشت» (Permutation) در ریاضیات، کار سازمان‌دهی اعضای یک مجموعه در توالی یا ترتیب‌ها است. اگر مجموعه خود مرتب باشد، باز سازمان‌دهی (مرتب‌سازی مجدد) عناصر آن با اهداف گوناگون انجام می‌شود که به این فرایند، جایگشت می‌گویند. جایگشت با «ترکیب» (Combinations) که انتخاب از میان اعضای مجموعه، صرف نظر از ترتیب آن‌ها است، به طور کامل تفاوت دارد. یک رشته با طول n، دارای !n جایگشت است. در این مطلب، روش نوشتن برنامه چاپ جایگشت های رشته تشریح شده است. در ادامه، جایگشت‌های گوناگون رشته ABC را می‌توان مشاهده کرد.

ABC ACB BAC BCA CBA CAB

در تصویر زیر، راهکار مورد استفاده برای به دست آوردن جایگشت‌های مختلف رشته ABC با استفاده از روش «پَس‌گرد» (Backtracking) قابل مشاهده است. در ادامه، پیاده‌سازی روش مذکور با استفاده از زبان‌های برنامه‌نویسی گوناگون، شامل «سی‌پلاس‌پلاس» (++C ،(C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

برنامه چاپ جایگشت های رشته در ++C

1// C++ program to print all  
2// permutations with duplicates allowed  
3#include <bits/stdc++.h> 
4using namespace std; 
5  
6  
7// Function to print permutations of string  
8// This function takes three parameters:  
9// 1. String  
10// 2. Starting index of the string  
11// 3. Ending index of the string.  
12void permute(string a, int l, int r)  
13{  
14    // Base case  
15    if (l == r)  
16        cout<<a<<endl;  
17    else
18    {  
19        // Permutations made  
20        for (int i = l; i <= r; i++)  
21        {  
22  
23            // Swapping done  
24            swap(a[l], a[i]);  
25  
26            // Recursion called  
27            permute(a, l+1, r);  
28  
29            //backtrack  
30            swap(a[l], a[i]);  
31        }  
32    }  
33}  
34  
35// Driver Code  
36int main()  
37{  
38    string str = "ABC";  
39    int n = str.size();  
40    permute(str, 0, n-1);  
41    return 0;  
42}  
43  
44// This is code is contributed by rathbhupendra 

برنامه چاپ جایگشت های رشته در C

1// C program to print all permutations with duplicates allowed 
2#include <stdio.h> 
3#include <string.h> 
4  
5/* Function to swap values at two pointers */
6void swap(char *x, char *y) 
7{ 
8    char temp; 
9    temp = *x; 
10    *x = *y; 
11    *y = temp; 
12} 
13  
14/* Function to print permutations of string 
15   This function takes three parameters: 
16   1. String 
17   2. Starting index of the string 
18   3. Ending index of the string. */
19void permute(char *a, int l, int r) 
20{ 
21   int i; 
22   if (l == r) 
23     printf("%s\n", a); 
24   else
25   { 
26       for (i = l; i <= r; i++) 
27       { 
28          swap((a+l), (a+i)); 
29          permute(a, l+1, r); 
30          swap((a+l), (a+i)); //backtrack 
31       } 
32   } 
33} 
34  
35/* Driver program to test above functions */
36int main() 
37{ 
38    char str[] = "ABC"; 
39    int n = strlen(str); 
40    permute(str, 0, n-1); 
41    return 0; 
42}

برنامه چاپ جایگشت های رشته در جاوا

1// Java program to print all permutations of a 
2// given string. 
3public class Permutation 
4{ 
5    public static void main(String[] args) 
6    { 
7        String str = "ABC"; 
8        int n = str.length(); 
9        Permutation permutation = new Permutation(); 
10        permutation.permute(str, 0, n-1); 
11    } 
12  
13    /** 
14     * permutation function 
15     * @param str string to calculate permutation for 
16     * @param l starting index 
17     * @param r end index 
18     */
19    private void permute(String str, int l, int r) 
20    { 
21        if (l == r) 
22            System.out.println(str); 
23        else
24        { 
25            for (int i = l; i <= r; i++) 
26            { 
27                str = swap(str,l,i); 
28                permute(str, l+1, r); 
29                str = swap(str,l,i); 
30            } 
31        } 
32    } 
33  
34    /** 
35     * Swap Characters at position 
36     * @param a string value 
37     * @param i position 1 
38     * @param j position 2 
39     * @return swapped string 
40     */
41    public String swap(String a, int i, int j) 
42    { 
43        char temp; 
44        char[] charArray = a.toCharArray(); 
45        temp = charArray[i] ; 
46        charArray[i] = charArray[j]; 
47        charArray[j] = temp; 
48        return String.valueOf(charArray); 
49    } 
50  
51} 
52  
53// This code is contributed by Mihir Joshi 

برنامه چاپ جایگشت های رشته در پایتون

1# Python program to print all permutations with
2# duplicates allowed
3
4def toString(List):
5	return ''.join(List)
6
7# Function to print permutations of string
8# This function takes three parameters:
9# 1. String
10# 2. Starting index of the string
11# 3. Ending index of the string.
12def permute(a, l, r):
13	if l==r:
14		print (toString(a))
15	else:
16		for i in range(l,r):
17			a[l], a[i] = a[i], a[l]
18			permute(a, l+1, r)
19			a[l], a[i] = a[i], a[l] # backtrack
20
21# Driver program to test the above function
22string = "ABC"
23n = len(string)
24a = list(string)
25permute(a, 0, n)
26
27# This code is contributed by Bhavya Jain

برنامه چاپ جایگشت های رشته در #C

1// C# program to print all  
2// permutations of a given string. 
3using System; 
4  
5class GFG 
6{ 
7    /** 
8    * permutation function 
9    * @param str string to  
10       calculate permutation for 
11    * @param l starting index 
12    * @param r end index 
13    */
14    private static void permute(String str, 
15                                int l, int r) 
16    { 
17        if (l == r) 
18            Console.WriteLine(str); 
19        else
20        { 
21            for (int i = l; i <= r; i++) 
22            { 
23                str = swap(str, l, i); 
24                permute(str, l + 1, r); 
25                str = swap(str, l, i); 
26            } 
27        } 
28    } 
29  
30    /** 
31    * Swap Characters at position 
32    * @param a string value 
33    * @param i position 1 
34    * @param j position 2 
35    * @return swapped string 
36    */
37    public static String swap(String a,  
38                              int i, int j) 
39    { 
40        char temp; 
41        char[] charArray = a.ToCharArray(); 
42        temp = charArray[i] ; 
43        charArray[i] = charArray[j]; 
44        charArray[j] = temp; 
45        string s = new string(charArray); 
46        return s; 
47    } 
48  
49// Driver Code 
50public static void Main() 
51{ 
52    String str = "ABC"; 
53    int n = str.Length; 
54    permute(str, 0, n-1); 
55} 
56} 
57  
58// This code is contributed by mits

برنامه چاپ جایگشت های رشته در PHP

1<?php 
2// PHP program to print all  
3// permutations of a given string. 
4  
5  
6/** 
7* permutation function 
8* @param str string to  
9*  calculate permutation for 
10* @param l starting index 
11* @param r end index 
12*/
13function permute($str, $l, $r) 
14{ 
15    if ($l == $r) 
16        echo $str. "\n"; 
17    else
18    { 
19        for ($i = $l; $i <= $r; $i++) 
20        { 
21            $str = swap($str, $l, $i); 
22            permute($str, $l + 1, $r); 
23            $str = swap($str, $l, $i); 
24        } 
25    } 
26} 
27  
28/** 
29* Swap Characters at position 
30* @param a string value 
31* @param i position 1 
32* @param j position 2 
33* @return swapped string 
34*/
35function swap($a, $i, $j) 
36{ 
37    $temp; 
38    $charArray = str_split($a); 
39    $temp = $charArray[$i] ; 
40    $charArray[$i] = $charArray[$j]; 
41    $charArray[$j] = $temp; 
42    return implode($charArray); 
43} 
44  
45// Driver Code 
46$str = "ABC"; 
47$n = strlen($str); 
48permute($str, 0, $n - 1); 
49  
50// This code is contributed by mits. 
51?>

خروجی

خروجی قطعه کدهای بالا، برای رشته ABC، در ادامه ارائه شده است.

ABC
ACB
BAC
BCA
CBA
CAB

پیچیدگی زمانی الگوریتم پس‌گرد مورد استفاده برای حل این مساله، از درجه (!O(n*n است. توجه به این نکته لازم است که !n جایگشت وجود دارد و نیازمند زمان (O(n برای چاپ کردن جایگشت است.

راهکار بالا، در صورت وجود کاراکتر تکراری در رشته ورودی، جایگشت‌های تکراری را در خروجی چاپ می‌کند. می‌توان الگوریتم را به نوعی بهبود بخشید که تنها جایگشت‌های متمایز را چاپ کند؛ حتی در صورتی که تکرار در رشته ورودی وجود داشته باشد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۲ دیدگاه برای «برنامه چاپ جایگشت های رشته — به زبان ساده»

خروجی کد پایتون اشتباه هست
xrange تعریف نشده.

سلام، وقت شما بخیر؛

از گزارش این مورد بسیار سپاسگزاریم. کد پایتون بازنگری و مجدداً درج شده است.

از همراهی شما با مجله فرادرس بسیار خرسندیم.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *