Sortir angka yang direpresentasikan dalam basis yang tidak diketahui

13

Diberikan daftar string, urutkan daftar sebagai angka tanpa mengetahui basis apa yang digunakan. Nilai digit juga tidak diketahui (mungkin saja '1'>'2' ).

Karena nilai digit tidak diketahui, gunakan Hukum Benford (atau Hukum Digit Pertama) untuk menentukan nilai relatif digit tersebut. Untuk distribusi yang mengikuti Hukum Benford, digit bernilai rendah muncul sebagai digit utama lebih sering daripada digit bernilai tinggi.

Aturan

  • Ini adalah kode-golf
  • Daftar string dapat berasal dari sumber yang Anda pilih (stdin, variabel, file, pengguna, dll.)
  • String terbatas pada karakter ASCII.
  • Karakter yang tidak muncul sebagai karakter utama memiliki nilai tertinggi. (anggap tidak ada nol, dan urutkan secara ketat berdasarkan frekuensi yang dipimpin.)
  • Karakter yang muncul sebagai angka di depan sama dengan jumlah kali karakter lainnya.

Contoh

Tidak disortir

['c','ca','ac','cc','a','ccc','cx','cz','cy']

Diurutkan

['c','a','cc','ca','cz','cy','cx','ac','ccc']

Catatan: Dalam contoh ini, 'cz', 'cy'dan 'cx'dapat muncul sebagai 5, 6 dan elemen-7 di urutan sejak digit 'x', 'y'dan 'z'sama-sama berbobot.

code-golf Rynant
sumber
"String dibatasi untuk karakter ASCII." Contoh Anda hanya menampilkan alfanumerik (sebenarnya hanya karakter alfabet). Maksud Anda semua karakter ASCII, atau hanya [0-9a-zA-Z], dan apakah huruf kecil menghitung sama atau berbeda dari karakter huruf besar?
Joshua Taylor
Semua karakter ASCII harus didukung, dan huruf besar dan kecil berbeda.
Rynant

Jawaban:

7

Python, 59 108 112

sorted(a,None,lambda x:(-len(x),map(zip(*a)[0].count,x)),1)

Input diberikan sebagai daftar a, dan ungkapan ini menghasilkan daftar yang diurutkan (+2 karakter untuk ditetapkan ke variabel). Ini mengurutkan daftar secara terbalik dengan panjang dinegasikan dan kemudian oleh frekuensi.

nneonneo
sumber
+1 Sudah selesai. Tidak mengira itu bisa dilakukan ruang efisien dalam ekspresi tunggal.
seequ
Bagus! Saya tidak tahu tentang zipdengan None. Meskipun tidak berfungsi di Python 3 yang akan digunakan itertools.zip_longest.
Rynant
Nonetidak dapat dibandingkan dengan bilangan bulat di Python 3, jadi itu akan gagal juga.
nneonneo
@nneonneo Benar, fillvalueharus diatur ke sesuatu yang kurang dari nilai terkecil.
Rynant
Dan saya pikir saya tahu sesuatu tentang python - nggak. Bisakah Anda menjelaskan kode Anda lebih detail? Saya akan sangat senang - pemula python di sini.
flawr
3

Ruby, 65

f=->a{a.sort_by{|s|[s.size,s.chars.map{|c|a.count{|t|t[0]!=c}}]}}

Mengurutkan secara leksikografis pada ukuran string, lalu frekuensi masing-masing karakter bukan digit terdepan.

histokrat
sumber
0

Jawa (261)

void s(String[]s){int[]a=new int[128];for(String t:s)a[t.charAt(0)]++;java.util.Arrays.sort(s,(o,p)->{int j=o.length()-p.length();if(j!=0)return j;for(int i=0;i<Math.min(o.length(),p.length());i++){j=a[p.charAt(i)]-a[o.charAt(i)];if(j!=0)return j;}return 0;});}

void s(String[] s) {
    int[] a = new int[128];
    for (String t : s) {
        a[t.charAt(0)]++;
    }
    java.util.Arrays.sort(s, (o, p) -> {
        int j = o.length() - p.length();
        if (j != 0) {
            return j;
        }
        for (int i = 0; i < Math.min(o.length(), p.length()); i++) {
            j = a[p.charAt(i)] - a[o.charAt(i)];
            if (j != 0) {
                return j;
            }
        }
        return 0;
    });
}

Metode mengambil array string, dan mengurutkan array di tempatnya. Tidak ada yang mewah tentang implementasinya, tetapi ia menggunakan ekspresi lambda yang ditambahkan ke Java 8.

Ypnypn
sumber
0

Javascript (E6) 147

F=i=>(f={},i.map(x=>(f[x[0]]=-~f[x[0]])),i.map(x=>[x,[...x].map(y=>1e9-~f[y]+'')]).sort((a,b,d=a[0].length-b[0].length)=>d||a[1]<b[1]).map(x=>x[0]))

Membatasi

Nilai frekuensi hingga 1000000000: untuk pengurutan, nilai frekuensi digabungkan dalam string yang besar

Tidak disatukan

F=i=>(
  f={}, //init frequency map
  i.map(x => (f[x[0]]=-~f[x[0]])), // build frequency map
  i.map(x => [x, [...x].map(y=>1e9-~f[y]+'')]) // add frequency info to each element of input list
 .sort((a,b,d=a[0].length-b[0].length)=>d || a[1]<b[1]) // then sort by lenght and frequency
 .map( x => x[0]) // throw away frequency info
)

Sidenote X-~ bertambah 1 bahkan jika angka asli X tidak terdefinisi atau NaN

Pemakaian

F(['c','ca','ac','cc','a','ccc','cx','cz','cy'])

Keluaran: ["c", "a", "cc", "ca", "cx", "cz", "cy", "ac", "ccc"]

edc65
sumber