シャッフルリストは、URLのリストでは、同様の要素

Question

間の距離を最大化するために、Sなどは、これはする必要があります安くても最適である必要はありません。 （私はウェブサイトa.com、b.com、c.comからファイルをダウンロードするためにURLのリストを使用しており、必要以上の頻度で特定のサイトを訪れたくないという例です。ここの例では、b.comサイトを3回連続してヒットしますこれは避けてください）。

私は理想的にはJavaライブラリが好きですが、疑似コードを解決します。 Maximise sum of pairwise distances in arrayは同様の問題だと思われますが、単純な答えはありませんでした。私は単に「十分に良い」ものを求めています。

Answer 1

答えが無かったので、私は自分自身を書きました。それは非常に原油ですが、動作します。それは、URLのリストを読み取り、ホストを抽出し、それらを数え、ホストの逆数に比例するインデックスでピジョンホール配列を塗りつぶします。私たちは余分なpigeonholesを必要とした場合の

package org.xmlcml.cmine.util; 

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

import org.apache.log4j.Level; 
import org.apache.log4j.Logger; 

import com.google.common.collect.HashMultiset; 
import com.google.common.collect.Multiset; 

public class URLShuffler { 

    public static final Logger LOG = Logger.getLogger(URLShuffler.class); 
    static { 
     LOG.setLevel(Level.DEBUG); 
    } 

//しかし、グアバの並べ替えを包む便利なメソッドであるメディアの問題

private static int TOL = 1; 
    private List<String> urls; 
    private Multiset<String> domains; 
    private Map<String, Integer> currentIndexByDomain; 
    private Map<String, Integer> countByDomain; 
    private List<String> outputUrls; 

    public URLShuffler() { 

    } 

    public void readURLs(List<String> urls) { 
     this.urls= urls; 
     domains = HashMultiset.create(); 
     for (String url : urls) { 
      String domain = getDomain(url); 
      domains.add(domain); 
     } 
     LOG.debug(domains); 
    } 

// this would be better using java.net.URL 

    private String getDomain(String url) { 
     int idx = url.indexOf("//"); 
     if (idx != -1) { 
      url = url.substring(idx+2); 
     } 
     idx = url.indexOf("/"); 
     String domain = url.substring(0, idx); 
     return domain; 
    } 

    public List<String> getShuffledUrls() { 
     currentIndexByDomain = new HashMap<String, Integer>(); 
     countByDomain = new HashMap<String, Integer>(); 

     outputUrls = new ArrayList<String>(); 
     for (int i = 0; i < urls.size() * TOL; i++) { 
      outputUrls.add(""); 
     } 

//のためにいないようです。

 for (Multiset.Entry<String> entry : CMineUtil.getEntriesSortedByCount(domains)) { 
      LOG.debug(entry); 
      countByDomain.put(entry.getElement(), entry.getCount()); 
      currentIndexByDomain.put(entry.getElement(), entry.getCount() - 1); 
     } 
     for (String url : urls) { 
      String domain = getDomain(url); 
      Integer currentIndex = currentIndexByDomain.get(domain); 
      Integer count = countByDomain.get(domain); 
      int slot = (urls.size() * currentIndex * TOL)/count; 
      currentIndexByDomain.put(domain, currentIndex - 1); 
      addUrl(url, slot); 
     } 
     return outputUrls; 
    } 

    private void addUrl(String url, int slot) { 
     boolean filled = fillLower(url, slot); 
     if (!filled) { 
      fillUpper(url, slot); 
     } 
    } 

// if slot is not free run upwards till next free slot 

    private boolean fillUpper(String url, int slot) { 
     for (int i = slot; i < outputUrls.size(); i++) { 
      if (fill(url, i)) { 
       return true; 
      } 
     } 
     return false; 
    } 

// if slot is not free run downwards till next free slot 
    private boolean fillLower(String url, int slot) { 
     for (int i = slot; i >= 0; i--) { 
      if (fill(url, i)) { 
       return true; 
      } 
     } 
     return false; 
    } 

    private boolean fill(String url, int slot) { 
     if (outputUrls.get(slot).equals("")) { 
      outputUrls.set(slot, url); 
      return true; 
     } 
     return false; 
    } 
} 

`` `