โปรแกรม C เพื่อค้นหาพีชคณิตของสตริงที่กำหนด

สมมติว่าเรามีสตริงไม่กี่สตริงในอาร์เรย์ เราจะต้องค้นหาการเรียงสับเปลี่ยนทั้งหมดของพวกเขาในบรรทัดที่แตกต่างกัน

ดังนั้น หากอินพุตเป็นเหมือน strings =["abc", "def", "ghi"] ผลลัพธ์จะเป็น

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน next_permutation() ซึ่งจะใช้ n, string array s,
• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i> 0 อัปเดต (ลด i โดย 1) ทำ:
  • ถ้า s[i]> s[i - 1]) แล้ว:
    • j :=ผม + 1
  • สำหรับ j
  • ถ้า s[j] <=s[i - 1]) แล้ว:
    • ออกมาจากวงจร
  • t :=s[i - 1]
• s[i - 1] =s[j - 1]
• s[j - 1] =t
• สำหรับ i
• t :=s[i]
• s[i] :=s[n - 1]
• s[n - 1] =t

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <stdio.h>
#include <string.h>
int next_permutation(int n, char **s){
    for (int i = n - 1; i > 0; i--)
        if (strcmp(s[i], s[i - 1]) > 0){
            int j = i + 1;
            for (; j < n; j++)
                if (strcmp(s[j], s[i - 1]) <= 0)
                    break;
            char *t = s[i - 1];
            s[i - 1] = s[j - 1];
            s[j - 1] = t;
            for (; i < n - 1; i++, n--){
                t = s[i];
                s[i] = s[n - 1];
                s[n - 1] = t;
            }
            return 1;
        }
    for (int i = 0; i < n - 1; i++, n--){
        char *t = s[i];
        s[i] = s[n - 1];
        s[n - 1] = t;
    }
    return 0;
}
int main(){
    char *strings[] = {"abc", "def", "ghi"};
    int n = 3;
    do{
        for (int i = 0; i < n; i++)
            printf("%s%c", strings[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, strings));
}

อินพุต

{"abc", "def", "ghi"}

ผลลัพธ์

abc def ghi
abc ghi def
def abc ghi
def ghi abc
ghi abc def
ghi def abc