Permutations of the rows in a matrix of characters

Question

For a 6x6 matrix of characters, or really an array of 6 strings, I need to find all possible six-character strings that can be formed along the main diagonal (\).

So for the matrix

[[a[0], a[1], a[2], a[3], a[4], a[5]]
[b[0], b[1], b[2], b[3], b[4], b[5]]
[c[0], c[1], c[2], c[3], c[4], c[5]]
[d[0], d[1], d[2], d[3], d[4], d[5]]
[e[0], e[1], e[2], e[3], e[4], e[5]]
[f[0], f[1], f[2], f[3], f[4], f[5]]]

Where each a0, b1, c2,... is a character, I need to print all the possible strings that come from combining the characters along the diagonal from top left to bottom right, e.g. "a[0] + b[1] + c[2] + d[3] + e[4] + f[5]".

The different combinations come from different positions of strings in the matrix, like [a,b,c,d,e,f], [b,a,c,d,e,f], [f,d,e,b,a,c], and so on. As far as I can tell there are 720 possible output strings (6!).

I only know a little of each Java and Python, but I feel like there's a pretty simple solution I can do with for loops. Any ideas?

Are you asking how to extract these characters from the array of strings, or how to find all permutations of those six characters, or both? — aliteralmind, Mar 25 '14 at 23:58
if you try with a 3x3 matrix first, it's faster to try things and understand the problem and to find a solution. — Leo, Mar 25 '14 at 23:58

score 0 · Answer 1 · edited May 23 '17 at 10:31

Assuming each string in the array has the exact same number of characters as the string array has elements, then extracting the diagonal characters is just a matter of looping through

sixStrings[index].charAt(index);

Because of your diagonal requirement, the only counter you need to keep track of is the single index. That same index is used as both the string-index and the sub-char index. Just put each into a new char array of the same length (and at that same index).

As far as finding all possible permutations of those six characters, see this question, which answers the question both language-antagonistically, and also specifically for Java: Generate list of all possible permutations of a string

score 0 · Answer 2 · answered Mar 26 '14 at 00:10

It can be done very easily with recursion.

import java.util.ArrayList;
import java.util.List;

public class JavaApplication120 {

    public static void main(String[] args) {
        String[] array = {"asfghl", "qwndof", "zzetil", "bbbdie", "apqith", "nzivhe"};
        String diagonal = "";
        for (int i = 0; i < array.length; i++) {
            diagonal += array[i].charAt(i);
        }

        List<String> permutations = allPermutation("", diagonal);
        System.out.println("size is : " + permutations.size());
        System.out.println(permutations);
    }

    public static List<String> allPermutation(String permutation, String letters) {
        List<String> list = new ArrayList<>();
        if (letters.isEmpty()) {
            list.add(permutation);
            return list;
        }

        for (int i = 0; i < letters.length(); i++) {
            list.addAll(allPermutation(permutation + letters.charAt(i), removeCharAt(i, letters)));
        }

        return list;
    }

    public static String removeCharAt(int pos, String text) {
        return text.substring(0, pos) + text.substring(pos + 1, text.length());
    }
}

Output for this program is :

size is : 720
[awedte, awedet, awetde, aweted, aweedt, aweetd, awdete, awdeet, awdtee, awdtee, awdeet, awdete, awtede, awteed, awtdee, awtdee, awteed, awtede, aweedt, aweetd, awedet, awedte, aweted, awetde, aewdte, aewdet, aewtde, aewted, aewedt, aewetd, aedwte, aedwet, aedtwe, aedtew, aedewt, aedetw, aetwde, aetwed, aetdwe, aetdew, aetewd, aetedw, aeewdt, aeewtd, aeedwt, aeedtw, aeetwd, aeetdw, adwete, adweet, adwtee, adwtee, adweet, adwete, adewte, adewet, adetwe, adetew, adeewt, adeetw, adtwee, adtwee, adtewe, adteew, adtewe, adteew, adewet, adewte, adeewt, adeetw, adetwe, adetew, atwede, atweed, atwdee, atwdee, atweed, atwede, atewde, atewed, atedwe, atedew, ateewd, ateedw, atdwee, atdwee, atdewe, atdeew, atdewe, atdeew, atewed, atewde, ateewd, ateedw, atedwe, atedew, aewedt, aewetd, aewdet, aewdte, aewted, aewtde, aeewdt, aeewtd, aeedwt, aeedtw, aeetwd, aeetdw, aedwet, aedwte, aedewt, aedetw, aedtwe, aedtew, aetwed, aetwde, aetewd, aetedw, aetdwe, aetdew, waedte, waedet, waetde, waeted, waeedt, waeetd, wadete, wadeet, wadtee, wadtee, wadeet, wadete, watede, wateed, watdee, watdee, wateed, watede, waeedt, waeetd, waedet, waedte, waeted, waetde, weadte, weadet, weatde, weated, weaedt, weaetd, wedate, wedaet, wedtae, wedtea, wedeat, wedeta, wetade, wetaed, wetdae, wetdea, wetead, weteda, weeadt, weeatd, weedat, weedta, weetad, weetda, wdaete, wdaeet, wdatee, wdatee, wdaeet, wdaete, wdeate, wdeaet, wdetae, wdetea, wdeeat, wdeeta, wdtaee, wdtaee, wdteae, wdteea, wdteae, wdteea, wdeaet, wdeate, wdeeat, wdeeta, wdetae, wdetea, wtaede, wtaeed, wtadee, wtadee, wtaeed, wtaede, wteade, wteaed, wtedae, wtedea, wteead, wteeda, wtdaee, wtdaee, wtdeae, wtdeea, wtdeae, wtdeea, wteaed, wteade, wteead, wteeda, wtedae, wtedea, weaedt, weaetd, weadet, weadte, weated, weatde, weeadt, weeatd, weedat, weedta, weetad, weetda, wedaet, wedate, wedeat, wedeta, wedtae, wedtea, wetaed, wetade, wetead, weteda, wetdae, wetdea, eawdte, eawdet, eawtde, eawted, eawedt, eawetd, eadwte, eadwet, eadtwe, eadtew, eadewt, eadetw, eatwde, eatwed, eatdwe, eatdew, eatewd, eatedw, eaewdt, eaewtd, eaedwt, eaedtw, eaetwd, eaetdw, ewadte, ewadet, ewatde, ewated, ewaedt, ewaetd, ewdate, ewdaet, ewdtae, ewdtea, ewdeat, ewdeta, ewtade, ewtaed, ewtdae, ewtdea, ewtead, ewteda, eweadt, eweatd, ewedat, ewedta, ewetad, ewetda, edawte, edawet, edatwe, edatew, edaewt, edaetw, edwate, edwaet, edwtae, edwtea, edweat, edweta, edtawe, edtaew, edtwae, edtwea, edteaw, edtewa, edeawt, edeatw, edewat, edewta, edetaw, edetwa, etawde, etawed, etadwe, etadew, etaewd, etaedw, etwade, etwaed, etwdae, etwdea, etwead, etweda, etdawe, etdaew, etdwae, etdwea, etdeaw, etdewa, eteawd, eteadw, etewad, etewda, etedaw, etedwa, eeawdt, eeawtd, eeadwt, eeadtw, eeatwd, eeatdw, eewadt, eewatd, eewdat, eewdta, eewtad, eewtda, eedawt, eedatw, eedwat, eedwta, eedtaw, eedtwa, eetawd, eetadw, eetwad, eetwda, eetdaw, eetdwa, dawete, daweet, dawtee, dawtee, daweet, dawete, daewte, daewet, daetwe, daetew, daeewt, daeetw, datwee, datwee, datewe, dateew, datewe, dateew, daewet, daewte, daeewt, daeetw, daetwe, daetew, dwaete, dwaeet, dwatee, dwatee, dwaeet, dwaete, dweate, dweaet, dwetae, dwetea, dweeat, dweeta, dwtaee, dwtaee, dwteae, dwteea, dwteae, dwteea, dweaet, dweate, dweeat, dweeta, dwetae, dwetea, deawte, deawet, deatwe, deatew, deaewt, deaetw, dewate, dewaet, dewtae, dewtea, deweat, deweta, detawe, detaew, detwae, detwea, deteaw, detewa, deeawt, deeatw, deewat, deewta, deetaw, deetwa, dtawee, dtawee, dtaewe, dtaeew, dtaewe, dtaeew, dtwaee, dtwaee, dtweae, dtweea, dtweae, dtweea, dteawe, dteaew, dtewae, dtewea, dteeaw, dteewa, dteawe, dteaew, dtewae, dtewea, dteeaw, dteewa, deawet, deawte, deaewt, deaetw, deatwe, deatew, dewaet, dewate, deweat, deweta, dewtae, dewtea, deeawt, deeatw, deewat, deewta, deetaw, deetwa, detawe, detaew, detwae, detwea, deteaw, detewa, tawede, taweed, tawdee, tawdee, taweed, tawede, taewde, taewed, taedwe, taedew, taeewd, taeedw, tadwee, tadwee, tadewe, tadeew, tadewe, tadeew, taewed, taewde, taeewd, taeedw, taedwe, taedew, twaede, twaeed, twadee, twadee, twaeed, twaede, tweade, tweaed, twedae, twedea, tweead, tweeda, twdaee, twdaee, twdeae, twdeea, twdeae, twdeea, tweaed, tweade, tweead, tweeda, twedae, twedea, teawde, teawed, teadwe, teadew, teaewd, teaedw, tewade, tewaed, tewdae, tewdea, tewead, teweda, tedawe, tedaew, tedwae, tedwea, tedeaw, tedewa, teeawd, teeadw, teewad, teewda, teedaw, teedwa, tdawee, tdawee, tdaewe, tdaeew, tdaewe, tdaeew, tdwaee, tdwaee, tdweae, tdweea, tdweae, tdweea, tdeawe, tdeaew, tdewae, tdewea, tdeeaw, tdeewa, tdeawe, tdeaew, tdewae, tdewea, tdeeaw, tdeewa, teawed, teawde, teaewd, teaedw, teadwe, teadew, tewaed, tewade, tewead, teweda, tewdae, tewdea, teeawd, teeadw, teewad, teewda, teedaw, teedwa, tedawe, tedaew, tedwae, tedwea, tedeaw, tedewa, eawedt, eawetd, eawdet, eawdte, eawted, eawtde, eaewdt, eaewtd, eaedwt, eaedtw, eaetwd, eaetdw, eadwet, eadwte, eadewt, eadetw, eadtwe, eadtew, eatwed, eatwde, eatewd, eatedw, eatdwe, eatdew, ewaedt, ewaetd, ewadet, ewadte, ewated, ewatde, eweadt, eweatd, ewedat, ewedta, ewetad, ewetda, ewdaet, ewdate, ewdeat, ewdeta, ewdtae, ewdtea, ewtaed, ewtade, ewtead, ewteda, ewtdae, ewtdea, eeawdt, eeawtd, eeadwt, eeadtw, eeatwd, eeatdw, eewadt, eewatd, eewdat, eewdta, eewtad, eewtda, eedawt, eedatw, eedwat, eedwta, eedtaw, eedtwa, eetawd, eetadw, eetwad, eetwda, eetdaw, eetdwa, edawet, edawte, edaewt, edaetw, edatwe, edatew, edwaet, edwate, edweat, edweta, edwtae, edwtea, edeawt, edeatw, edewat, edewta, edetaw, edetwa, edtawe, edtaew, edtwae, edtwea, edteaw, edtewa, etawed, etawde, etaewd, etaedw, etadwe, etadew, etwaed, etwade, etwead, etweda, etwdae, etwdea, eteawd, eteadw, etewad, etewda, etedaw, etedwa, etdawe, etdaew, etdwae, etdwea, etdeaw, etdewa]

Permutations of the rows in a matrix of characters

2 Answers2