根据字母顺序查找字符串的 "permutation"

Question

我想请教一下，是否有更有效的方法来根据字母顺序查找字符串的排列，就像我下面的代码一样。我正在处理长达 16 个字符的字符串和大量数据，并且运行我的程序占用了太多时间和内存。

问题的基本表示

输入：字母表

输出：16752348

所以单词"alphabet"中的字母'a'是字母表中的第一个，将其标记为索引1，然后在第五个位置出现另一个'a'，将其标记为2，然后'b' 排在第六位，标记为 3 以此类推..

在代码中我没有使用数字作为索引，而是使用字符，所以从 ASCII 值的值 65 开始。（因为我使用测试长字符串。但它不会改变主要目的）。所以我的程序的输出将是

输入：字母表

输出：AFGEBCDH

public static String perm(String word){

    char[] perm = new char[word.length()];
    char[] wordArray = word.toCharArray();
    char[] sortedWord = new char[word.length()];

    sortedWord = word.toCharArray();
    Arrays.sort(sortedWord);

    for (int i=0; i<word.length(); i++){
        for (int j=0; j<word.length(); j++){

            if (sortedWord[i] == wordArray[j]){
                perm[j] = (char)(65+i);  //from A
                wordArray[j] = '.';

                j = word.length();    //in case, if the word has more of the tested char, we jump to the end of the cycle
            }
        }
    }

    return String.valueOf(perm);
}

public static void main (String [] args){
    System.out.println(perm("alphabet"));
}

Answer 1

WRT内存占用，你贴的程序用不了多少。你在真正的代码中对返回的字符串做了什么？

就性能而言，这应该会好一点：

import java.util.Arrays;

class El implements Comparable<El>{
 char c;
 int idx;

 public El(char c, int idx) {
  this.c = c;
  this.idx = idx;
 }

 public int compareTo(El other) {
   return Character.compare(c, other.c);
 }
}

public class Perm {
  public static String perm(String word){
    int l = word.length();
    El[] els = new El[l];
    for (int i=0; i<l; i++) {
      els[i] = new El(word.charAt(i), i);
    }
    Arrays.sort(els);
    StringBuilder sb = new StringBuilder(l);
    for (int i=0; i<els.length; i++) {
      sb.append((char)('A' + els[i].idx));
    }
    return sb.toString();
  }

  public static void main (String [] args){
    System.out.println(perm("alphabet"));
  }
}

Answer 2

试试这个：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class alphabet {
    public static List<CharIndexHolder> charlist = new ArrayList<CharIndexHolder>();

    public static String perm(String word) {
        char[] perm = new char[word.length()];
        char[] wordArray = word.toCharArray();
        char[] sortedWord = new char[word.length()];

        sortedWord = word.toCharArray();
        Arrays.sort(sortedWord);

        for (int i=0; i<word.length(); i++){
            for (int j=0; j<word.length(); j++){

                if (sortedWord[i] == wordArray[j]){
                    perm[j] = (char)(65+i);  //from A
                    wordArray[j] = '.';

                    j = word.length();    //in case, if the word has more of the tested char, we jump to the end of the cycle
                }
            }
        }   
        return String.valueOf(perm);
    }

    public static String perm2(String word) {
        charlist.clear();
        for(int i = 0; i < word.length(); i++) {
            charlist.add(new CharIndexHolder(word.charAt(i), i));
        }
        Collections.sort(charlist);
        for(int i = 0; i < charlist.size(); i++) {
            charlist.get(i).assignedindex = i;
        }
        char[] result = new char[word.length()];
        for(int i = 0; i < result.length; i++) {
            CharIndexHolder cur = charlist.get(i);
            result[cur.index] =(char) (charlist.get(i).assignedindex + 65);
        }
        return new String(result);
    }

    public static void main (String [] args){
        System.out.println(perm("alphabet"));
        System.out.println(perm2("alphabet"));
    }
}

助手class:

public class CharIndexHolder implements Comparable<CharIndexHolder> {
    public int index;
    private char character;
    public int assignedindex;

    CharIndexHolder(Character character, int index) {
        this.character = character;
        this.index = index;
    }

    @Override
    public int compareTo(CharIndexHolder o) {
        if(this.character < o.character) {
            return -1;
        }
        if(this.character > o.character) {
            return 1;
        }
        if(this.index < o.index) {
            return -1;
        }
        if(this.index > o.index) {
            return 1;
        }
        return 0;
    }       
}

我想不出比 N*log(n) 更快的方法。如果您需要更快的速度，请尝试用长数组替换列表，但每批只分配一次数组（而不是每次调用一次）。

Answer 3

我查看了我以前的解决方案，Arrays.sort() 对于可比数组花费的时间比原始类型数组要长得多。我尝试了更多方法，以下是为大量单词提供更短时间的方法：

  public static String perm(String word){
    int l = word.length();
    int[] els = new int[l];
    for (int i=0; i<l; i++) {
      els[i] = (word.charAt(i) << 16) | i;
    }
    Arrays.sort(els);
    char[] sb = new char[l];
    for (int i=0; i<els.length; i++) {
      sb[i] = (char)('A' + els[i] & 0xFFFF);
    }
    return String.valueOf(sb);
  }

请注意，该方法隐含假设单词仅使用 UTF-16 编码的低 15 位（对于英文字母表中的单词为真）。

在内存利用率方面，您必须小心 Java 中的测量值。事实上，一种方法与另一种方法相比，内存利用率可能会飙升，这不一定是一个好的指标，因为内存可能会被垃圾收集。这里的所有方法都使用临时 arrays/objects ，在执行 perm() 后可用于垃圾回收（返回的字符串除外）。现在，如果您关心降低内存利用率以减少垃圾收集（从而提高性能），我怀疑最后一种方法应该会产生良好的结果，尽管我还没有测量过。

根据字母顺序查找字符串的 "permutation"

Finding strings' "permutation" based on alphabetical order

java

string

permutation