jumlah string, ketika setiap karakter harus muncul genap kali

Saya telah memukul tengkorak saya pada masalah ini untuk beberapa waktu sekarang, dan itu benar-benar mulai membuat saya frustrasi. Masalahnya adalah:

Saya memiliki satu set karakter, A, B, C, dan D. Saya harus mengatakan dalam berapa banyak cara string dapat dibangun dari karakter-karakter itu, kapan panjangnya ndan setiap karakter harus terjadi bahkan kali.

Misalnya, jawabannya n = 2adalah 4:

AA
BB
CC
DD

Jawabannya n = 4adalah 40. Beberapa dari string yang valid adalah:

AAAA
AABB
CACA
DAAD
BCCB

Saya terjebak dalam membuat logika. Saya merasa mungkin ada solusi DP untuk ini. Brute-memaksa jalan saya melalui ini keluar dari pertanyaan: jumlah solusi dengan cepat tumbuh menjadi jumlah besar.

Saya sudah mencoba menggambar semua jenis ide di atas kertas, tetapi tidak berhasil. Hampir semua ide yang harus saya buang karena kompleksitasnya terlalu besar. Solusinya harus efisien untuk n = 10^4.

Salah satu ide saya adalah untuk tidak pernah melacak string yang sebenarnya, tetapi hanya apakah setiap karakter telah muncul bahkan atau kali aneh. Saya tidak dapat menemukan cara untuk menerapkan logika ini.

Ada yang bisa bantu saya?

Atur f(n,d)sebagai fungsi yang memberikan jumlah permutasi ndengan panjang (genap) menggunakan dkarakter yang berbeda (yaitu d=4dalam kasus Anda).

Jelas f(0,d) = 1dan f(n,1) = 1karena hanya ada satu pengaturan ketika Anda hanya memiliki satu karakter, atau nol spasi.

Sekarang langkah induksi:

Untuk membuat string yang valid menggunakan dkarakter, ambil string dengan panjang genap yang lebih pendek menggunakan d-1karakter dan perbaiki hingga panjang dengan menambahkan kelipatan genap dari karakter baru ini. Jumlah pengaturan adalah choose(n,n_newdigits)karena Anda dapat memilih n_newdigittempat dari total panjang string untuk memiliki digit baru, dan sisanya diisi oleh string asli secara berurutan.

Untuk mengimplementasikan ini menggunakan rekursi naif di R, saya lakukan:

f <- function(n,d)
{
  if(n==0) return(1)
  if(d==1) return(1)
  retval=0
  for (i in seq(from=0, to=n, by=2)) retval=retval+f(n-i,d-1)*choose(n,i)
  return(retval)
}

f(4,4)
# 40    

f(500,4)
# 1.339386e+300 takes about 10 secs

untuk jenis angka yang Anda minati, saya akan berpikir bahwa akan lebih efisien untuk menyimpan angka dalam susunan dua dimensi, dan beralih dari peningkatan d, tetapi ini mungkin tergantung pada pilihan bahasa Anda.

Jawaban Miff jelas elegan. Karena saya sudah punya hampir selesai saya tetap memberikannya. Hal yang baik adalah saya mendapatkan hasil yang sama untuk n = 500 :-)

Biarkan d menjadi jumlah karakter berbeda yang diizinkan, d = 4 dalam kasus Anda.

Biarkan n menjadi panjang string, pada akhirnya Anda akan melihat nilai genap n.

Biarkan Anda menjadi jumlah karakter tidak berpasangan dalam string.

Misalkan N (n, d, u) adalah jumlah string panjang n, dibangun dari d karakter yang berbeda dan memiliki u karakter yang tidak berpasangan. Mari kita coba menghitung N.

Ada beberapa kasus sudut yang perlu diperhatikan:

u> d atau u> n => N = 0

u <0 => N = 0

n% 2! = u% 2 => N = 0.

Ketika melangkah dari n ke n + 1, Anda harus meningkat sebesar 1 atau menurun sebesar 1, jadi kami memiliki rekursi sesuai dengan

N (n, d, u) = f (N (n-1, d, u-1), N (n-1, d, u + 1))

Berapa banyak cara untuk mengurangi Anda satu per satu Ini mudah, karena kita harus memasangkan salah satu karakter yang tidak berpasangan, yang membuatnya hanya kamu. Jadi bagian ke-2 dari f akan membaca (u + 1) * N (n-1, d, u + 1), dengan peringatan tentu saja kita harus mengamati bahwa N = 0 jika u + 1> n-1 atau u +1> d.

Setelah kita memahami ini, mudah untuk melihat apa bagian pertama dari f adalah: dalam berapa banyak cara kita dapat meningkatkan kamu ketika ada u-1 karakter tidak berpasangan. Kita harus memilih salah satu (k- (u-1)) karakter yang dipasangkan.

Jadi dengan mempertimbangkan semua kasus sudut, rumus rekursif untuk N adalah

N (n, d, u) = (d- (u-1)) * N (n-1, d, u-1) + (u + 1) * N (n-1, d, u + 1)

Saya tidak akan membaca di http://en.wikipedia.org/wiki/Concrete_Mathematics cara mengatasi rekursi.

Sebagai gantinya saya menulis beberapa kode Java. Sekali lagi sedikit lebih canggung, seperti halnya Jawa karena verbositasnya. Tetapi saya memiliki motivasi untuk tidak menggunakan rekursi, karena jauh dari awal, setidaknya di Jawa, ketika tumpukan meluap pada level 500 atau 1000 tingkat bersarang.

Hasil untuk n = 500, d = 4 dan u = 0 adalah:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

dihitung dalam 0,2 detik, karena menghafal hasil antara. N (40000,4,0) dihitung dalam waktu kurang dari 5 detik. Kode juga di sini: http://ideone.com/KvB5Jv

import java.math.BigInteger;

public class EvenPairedString2 {
  private final int nChars;  // d above, number of different chars to use
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();

  public EvenPairedString2(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/
  // encodes for a fixed d the task to compute N(strlen,d,unpaired).  
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/
  // return corner case or memorized result or null  
  private BigInteger getMemoed(Task t) {
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }

    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }

  public int getCount() {
    return count;
  }

  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);

    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }

      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    EvenPairedString2 eps = new EvenPairedString2(nChars);

    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n", 
                      eps.getCount(), strlen, nChars, 
                      result); 
  }
}

Saya mencoba untuk menemukan solusi tetapi gagal dan mengajukan pertanyaan yang sama pada Mathematics.StackExchange . Berkat Rus May , berikut ini solusinya, dalam Common Lisp:

(defun solve (n)
  (if (evenp n)
      (/ (+ (expt 4 n) (* 4 (expt 2 n))) 8)
      0))

Ini selalu mengembalikan 0 untuk nilai ganjil dari n. Untuk n = 500, inilah output dengan SBCL :

* (time (solve 500))

    Evaluation took:
      0.000 seconds of real time
      0.000000 seconds of total run time (0.000000 user, 0.000000 system)
      100.00% CPU
      51,100 processor cycles
      0 bytes consed

    1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360