Làm thế nào để có được tất cả các mô hình có thể có của một mảng của các chữ cái

Question

thể trùng lặp:
Are there any better methods to do permutation of string?

phép nói rằng tôi có các chữ cái

abcd

và tôi muốn nhận được mọi mẫu/kết hợp có thể có của các chữ cái này trong một chuỗi dài 4 chữ cái.

aaaa

baaa

caaa

daaa

abaa

acaa

Acad

abba

v.v.

Tôi có thể sử dụng vòng lặp hoặc mẫu nào để liệt kê mọi kết hợp có thể?

Tôi đang viết điều này trong C#, nhưng các ví dụ trong C++ và javascript cũng được chào đón.

Ý tưởng hiện tại của tôi chỉ tăng một chữ cái cho mỗi chữ cái có thể. Sau đó, chuyển sang phải một lần và lặp lại. Điều này không bao gồm các mẫu như thế nào.

abba

Answer 1

Dưới đây là một chỉ với một vòng lặp for

var one = ['a','b','c','d']; 
var length = one.length; 
var total = Math.pow(length, length); 
var pow3 = Math.pow(length,3); 
var pow2 = Math.pow(length,2); 

for(var i = 0; i<total; i++) 
    console.log(one[Math.floor(i/pow3)], 
     one[Math.floor(i/pow2)%length], 
     one[Math.floor(i/length)%length], 
     one[i%length]); 

---

Dưới đây là một phương pháp hiệu quả đơn giản:

var one = ['a','b','c','d']; 
var i,j,k,l; 
var len = 4; 
for(i=0;i<len;i++) { 
    for(j=0;j<len;j++) { 
     for(k = 0; k < len; k++) { 
      for(l = 0; l<len; l++) { 
       console.log(one[i], one[j], one[k], one[l]); 
      } 
     } 
    } 
} 

tương tự C#:

 var one = new[] {'a','b','c','d'}; 
     var len = one.Length; 

     for(var i=0;i<len;i++) { 
      for(var j=0;j<len;j++) { 
       for(var k = 0; k < len; k++) { 
        for(var l = 0; l<len; l++) { 
         Console.Write(one[i] + one[j] + one[k] + one[l]); 
        } 
       } 
      } 
     } 

Answer 2

Tôi đã đến giải pháp javascript này bằng cách sử dụng đệ quy. anyway không thực sự đắt tiền với những khó khăn này (chỉ có 4^4 cuộc gọi)

(function() { 
    var combinations = []; 

    (function r(s) { 
     s = s || ''; 
     if (s.length === 4) { 
      combinations[combinations.length] = s; 
      return; 
     } 
     r(s + 'a'); 
     r(s + 'b'); 
     r(s + 'c'); 
     r(s + 'd'); 

    })(); 

    console.log(combinations); 
})(); 

Đầu ra là

["aaaa", "aaab", "aaac", "aaad",...., "dddc", "dddd"] 

Answer 3

Chỉ cần cho các heck của nó, đây là một giải pháp chung cho bất kỳ số lượng chữ cái trong javascript.

http://jsfiddle.net/U9ZkX/

Điều thú vị là, google chrome muốn dịch ra từ "Mã Lai".

var letters = ['a', 'b', 'c', 'd']; 
var letterCount = letters.length; 
var iterations = Math.pow(letterCount, letterCount); 

for (var i = 0; i < iterations; i++) { 
    var word = ""; 

    for (var j = 0; j < letterCount; j++) { 
     word += letters[Math.floor(i/Math.pow(letterCount, j)) % letterCount]; 
    } 

    document.write(word + "<br>"); 
} 

Answer 4

Một đệ quy C# thực hiện:

public IEnumerable<string> CreateCombinations(IEnumerable<char> input, int length) 
{ 
    foreach (var c in input) 
    { 
     if (length == 1) 
      yield return c.ToString(); 
     else 
     { 
      foreach (var s in CreateCombinations(input, length - 1)) 
       yield return c.ToString() + s; 
     } 
    } 
} 

nên cho phép bất kỳ số lượng ký tự và bất kỳ chiều dài chuỗi yêu cầu (tốt cho đến khi stack tràn :))

Sử dụng nó:

foreach (var s in CreateCombinations("abcd", 4)) 
{ 
    Console.WriteLine(s); 
} 

Kết quả bằng:

aaaa 
aaab 
aaac 
aaad 
aaba 
aabb 
aabc 
aabd 
aaca 
... 
dddd 

Answer 5

Một đơn giản, giải pháp javascript đơn giản (mùa với niềng răng để nếm):

var letters = ['a', 'b', 'c', 'd'], len=letters.length; 

for (var i=len; i--;) 
    for (var j=len; j--;) 
    for (var k=len; k--;) 
     for (var l=len; l--;) 
     console.log (letters[i] + letters[j] + letters[k] + letters[l]); 

Answer 6

Bạn có thể làm như vậy rất dễ dàng với LINQ:

string[] items = {"a", "b", "c", "d"}; 
var query = from i1 in items 
      from i2 in items 
      from i3 in items 
      from i4 in items 
      select i1 + i2 + i3 + i4; 

foreach(var result in query) 
    Console.WriteLine(result); 

Nếu bạn không biết trước của thời gian mà bạn muốn kết hợp bốn, bạn có thể tính toán các sản phẩm Cartesian tùy ý với công việc nhiều hơn một chút:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Answer 7

Sử dụng đệ quy, hành động đại biểu và Lambdas !!! (Chỉ để cho vui)

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApplication4 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<char> letters = new List<char>() { 'a', 'b', 'c', 'd' }; 
      List<string> words = new List<string>(); 
      Action<IEnumerable<char>, string, List<string>> recursiveLetter = null; 

      recursiveLetter = (availLetters, word, newWords) => 
      { 
       if (word.Length < availLetters.Count()) 
       { 
        availLetters.ToList() 
           .ForEach(currentletter => 
              recursiveLetter(availLetters, 
                  word + currentletter, 
                  newWords)); 
       } 
       else 
       { 
        newWords.Add(word); 
       } 
      }; 

      recursiveLetter(letters, string.Empty, words); // ALL THE MAGIC GO! 

      words.ForEach(word => Console.WriteLine(word)); 
      Console.ReadKey(); 
     } 
    } 
} 

Answer 8

An thực hiện trong C

#include <stdio.h> 
#define WORD_LEN 5 
#define ALPHA_LEN 4 

char alphabet[ALPHA_LEN] = {'a', 'b', 'c', 'd'}; 
int w[WORD_LEN] = {}; 

void print_word() { 
    int i; 
    char s[WORD_LEN + 1]; 
    for(i = 0; i < WORD_LEN; i++) { 
     s[i] = alphabet[w[i]]; 
    } 
    s[WORD_LEN] = '\0'; 
    puts(s); 
} 

int increment_word() { 
    int i; 
    for(i = 0; i < WORD_LEN; i++) { 
     if(w[i] < ALPHA_LEN - 1) { 
      w[i]++; 
      return 1; 
     } else { 
      w[i] = 0; 
     } 
    } 
    return 0; 
} 

int main() { 
    int i; 
    do { 
     print_word(); 
    } while (increment_word()); 
} 

Answer 9

Điều này có lẽ sẽ làm việc, quá;)

var letters = new[] {'a','b','c','d'}; 
Random random = new Random(); 
HashSet<string> results = new HashSet<string>(); 

while(results.Count < 256) { 
    results.Add(letters[random.Next(4)] + letters[random.Next(4)] 
       + letters[random.Next(4)] + letters[random.Next(4)]); 
} 

results.ToList().ForEach(Console.WriteLine); 

Answer 10

Một lót trong LINQ cho bất kỳ n đưa ra:

 var letters = new[] { "a", "b", "c", "d" }; 
     int n = 4; 

     var z = Enumerable.Range(1, n) 
      .Select(x => letters.AsEnumerable()) 
      .Aggregate((g,h) => g.Join(h, _ => true, _ => true, (a, b) => a + b)); 

Answer 11

Một câu trả lời dựa trên LINQ khác:

List<string> items = new List<string>() {"a", "b", "c", "d"}; 
items.ForEach(i1 => 
    items.ForEach(i2 => 
    items.ForEach(i3 => 
     items.ForEach(i4 => 
     Console.WriteLine(i1 + i2 + i3 + i4) 
    ) 
    ) 
) 
); 

Answer 12

Haskell cũng có thể có những chương trình ngắn nhất ở đây:

sequence (replicate 4 "abcd") 

replicate 4 "abcd" tạo ra một danh sách mà lặp đi lặp lại "abcd" bốn lần. sequence là một hoạt động rất đa hình, đa hình, có nhiều công dụng, trong đó tạo ra các sản phẩm Descartes trong danh sách các danh sách.

Có thể sao chép giải pháp này bằng C# hoặc các ngôn ngữ .NET khác. Giải pháp LINQ Eric Lippert của tương ứng với giải pháp Haskell này:

items = ["a", "b", "c", "d"] 

query = do i1 <- items 
      i2 <- items 
      i3 <- items 
      i4 <- items 
      return (i1 ++ i2 ++ i3 ++ i4) 

Nếu bạn so sánh chúng, tốt, lưu ý rằng LINQ của from ... in được lấy cảm hứng từ Haskell của <-, và LINQ của select là Haskell của return.

Mối quan hệ giữa các giải pháp một liner Haskell và còn ai có thể được đưa ra bằng cách viết định nghĩa riêng của chúng ta về sequence:

sequence' [] = return [] 
sequence' (m:ms) = do x <- m 
         xs <- sequence' ms 
         return (x:xs) 

Về LINQ, các sequence chức năng cho phép bạn thay thế lặp đi lặp lại from ix in items báo cáo chỉ với một danh sách các danh sách để chọn từng mục.

EDIT: một người bạn chỉ đánh tôi tại một xếp hàng này (tốt, một dòng ngoại trừ import):

import Control.Monad 

replicateM 4 "abcd" 

Answer 13

Trong Python:

mục = [ "a", "b", "c", "d"]

in [a + b + c + d cho một trong các mặt hàng cho b trong mục cho c trong mục cho d trong ite ms]

Answer 14

Bạn có bảng chữ cái với 2 chữ cái, vì vậy mọi chữ cái thể hiện chính xác hai bit và do đó đối với chữ cái thể hiện tám bit. Bây giờ nó là một vấn đề đơn giản liệt kê tất cả các giá trị. Trong pCeudocode:

static const char alphabet[4] = { 'a', 'b', 'c', 'd' }; 

for (unsigned int i = 0; i != 256; ++i) 
{ 
    for (unsigned int k = 0; k != 4; ++k) 
    { 
     print(alphabet[(i >> (2*k)) % 4]); 
    } 
} 

đây 256   = × , vì vậy bạn có thể dễ dàng khái quát chương trình này.

Answer 15

Phải có một danh sách erlang hiểu

Something như

Value = "abcd". 
[ [A] ++ [B] ++ [C] ++ [D] || A <- Value, B <- Value, C <- Value, D <- Value ].